Problem

给定一个用火柴棍摆出的 $n$ 位的数，问在最多移动 $m$ 次的情况下，能摆出的最大数。

Solution

分成两部分，数字 $1$ 被摆出需要的火柴棍最少，所以优先加位肯定是最好的，不会使答案变小。
这是贪心。
然后是一个数位 Dp，求出最多有多少火柴棍可以拆出来，用来加位。
设 $f_{p, ct}$ 表示从高往低到第 $p$ 位，已经确定用途的火柴棍有 $ct$ 根所需的火柴棍数。
于是 dfs，再从大往小枚举用来加位的火柴棍数，判断最终所需总火柴棍数是否不超过 $m$ 即可。
输出方案过程类似。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 5010, inf = 0x3f3f3f3f;

int n, m;
string str;
int f[N][M];
int trans[10][10] = {
	{0, 4, 2, 2, 3, 2, 1, 3, 0, 1},
	{0, 0, 1, 0, 0, 1, 1, 0, 0, 0},
	{1, 4, 0, 1, 3, 2, 1, 3, 0, 1},
	{1, 3, 1, 0, 2, 1, 1, 2, 0, 0},
	{1, 2, 2, 1, 0, 1, 1, 2, 0, 0},
	{1, 4, 2, 1, 2, 0, 0, 3, 0, 0},
	{1, 5, 2, 2, 3, 1, 0, 4, 0, 1},
	{0, 1, 1, 0, 1, 1, 0, 0, 0, 0},
	{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
	{1, 4, 2, 1, 2, 1, 1, 3, 0, 0}
};
int cnt[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int dfs(int p, int ct)
{
	if (ct > m) return inf;
	if (!p) return ct ? inf : 0;
	if (~f[p][ct]) return f[p][ct];
	
	f[p][ct] = inf;
	for (int i = 9; ~i; i -- )
	{
		int tmp = dfs(p - 1, ct + cnt[i] - cnt[str[p]]) + trans[str[p]][i];
		f[p][ct] = min(f[p][ct], tmp);
 	}
 	
 	return f[p][ct];
}

void put(int p, int ct)
{
	while (p)
	{
		for (int i = 9; ~i; i -- )
		{
			int t = dfs(p - 1, ct + cnt[i] - cnt[str[p]]) + trans[str[p]][i];
			if (t <= m)
			{
				cout << i;
				m -= trans[str[p]][i];
				ct += cnt[i] - cnt[str[p]];
				p -- ;
				break;
			}
		}
	}
}

signed main()
{
	cin >> str >> m;
	
	n = str.size();
	reverse(str.begin(), str.end());
	str = " " + str;
	memset(f, -1, sizeof f);
	for (int i = 1; i <= n; i ++ ) str[i] -= '0';
	for (int i = m; i > 1; i -- )
	{
		if (dfs(n, i) <= m)
		{
			int t = i;
			if (t & 1) cout << "7", t -= 3;
			while (t) cout << "1", t -= 2;
			put(n, i);
			return 0;
		}
	}
	
	put(n, 0);
	
	return 0;
}