题解：P3283 [SCOI2013] 火柴棍数字
XuYueming
·
·
题解
前言
不想写题解，但是题解区没有简短易懂的做法。
题目链接：洛谷。
更好的体验。
题意简述
给定火柴棒拼成的数字 x，你需要移动最多 k 根火柴棒，使数最大。
设 n 表示 x 的位数，1\leq n\leq500。
题目分析
如果得知了最终的数 y，怎么计算最小移动次数？
首先两者火柴棒根数必须相等。设 t 表示两个数按火柴棒异或后的火柴棒的数量（即 x 中某一个位置上有一根火柴棒，但在 y 中没有，反之亦然），t 显然是偶数，那么 \frac{t}{2} 就是最少移动次数。可以暴力打表找规律了。
枚举多出部分的火柴棒根数，这部分按火柴棒异或后的数量，就是枚举的火柴棒根数。需要检查剩下部分有没有合法方案。
进一步明确问题，设枚举的根数为 $i$，总火柴棒根数为 $\mathrm{tot}$。用 $\mathrm{tot}-i$ 根火柴棒，摆出长度为 $n$ 的数字，设其和 $x$ 按火柴棒异或后的根数为 $t$，求是否能使 $t+i\leq2k$。
这部分显然可以数位 DP 了。设 $f_{i,j}$ 表示用 $j$ 根火柴棒，摆出长度为 $i$ 的数字，和 $x$ 低 $i$ 位按位异或后根数的最小值。转移很简单。
最后输出方案贪心高位从大到小考虑是否存在合法方案即可。
时间复杂度在忽略对于本题来说一系列常数是 $\mathcal{O}(n^2)$。
## 代码
按火柴棒异或打 $10\times10$ 的表太傻了，把每个数字用到的火柴棒状压就行了。
```cpp
#include <cstdio>
#define popc __builtin_popcount
const int N = 5e2 + 10;
const int inf = 0x3f3f3f3f;
const int TOT = 3510;
const int c[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
const unsigned st[] = { 0b1011111, 0b0001100, 0b1111001, 0b1111100, 0b0101110,
0b1110110, 0b1110111, 0b1001100, 0b1111111, 0b1111110 };
inline int min(int a, int b) { return a < b ? a : b; }
int n, k;
char x[N];
short y[N];
bool _vf[N][TOT];
int f[N][TOT];
int dfs(int p, int tot) {
// 剩下 tot 根木棍，diff 的最小值
if (p == 0) return tot ? inf : 0;
if (_vf[p][tot]) return f[p][tot];
_vf[p][tot] = true;
int &o = f[p][tot] = inf;
for (int i = 0; i < 10; ++i)
if (tot >= c[i])
o = min(o, dfs(p - 1, tot - c[i]) + popc(st[y[p]] ^ st[i]));
return o;
}
void output(int tot, int cur) {
for (int p = n; p; --p) {
for (int o = 9; ~o; --o) {
if (tot < c[o]) continue;
int t = dfs(p - 1, tot - c[o]) + popc(st[y[p]] ^ st[o]);
if (t + cur <= k * 2) {
putchar(o | 48), tot -= c[o], cur += popc(st[y[p]] ^ st[o]);
break;
}
}
}
}
signed main() {
scanf("%s%d", x + 1, &k);
while (x[++n]);
--n;
int tot = 0;
for (int i = 1; i <= n; ++i) {
y[i] = x[n - i + 1] ^ 48;
tot += c[y[i]];
}
for (int i = min(k, tot); i >= 2; --i)
if (dfs(n, tot - i) + i <= 2 * k) {
int x = i;
if (x & 1) putchar('7'), x -= 3;
for (; x; x -= 2) putchar('1');
output(tot - i, i);
return 0;
}
dfs(n, tot);
output(tot, 0);
return 0;
}
```