比如月赛 div1 B subtask2,我原用状压 DP 来写,但记录路径的地方写挂了,只好换成 DFS 水了 subtask2 的分。
能简述一下这种题目状压 DP 怎么记录方案吗?
我的思路:每次记录使状态 S 达到最优解的最后一步,然后再按照该方案迭代,最后倒序输出。
reg int all = (1 << n) - 1;
memset(f, 0x3f, sizeof f), f[0] = 0;
for (reg int i = 2, d; i <= all; ++i) {
d = __builtin_popcount(i);
if (d & 1) continue;
for (reg int j = 1; j <= n; ++j)
if (i & (1 << j - 1)) for (reg int k = 1; k <= n; ++k)
if (j != k && x[j] != k && x[k] != j) {
ll tmp = f[i ^ (1 << j - 1) ^ (1 << k - 1)] + (ll)min(a[j], a[k]) * (d >> 1);
tmp < f[i] && (f[i] = tmp, jj[i][d >> 1] = j, kk[i][d >> 1] = k);
}
}
if (f[all] == 0x3f3f3f3f3f3f3f3f) puts("-1"), exit(0);
printf("%lld\n", f[all]);
for (reg int i = n >> 1; i; --i)
J[i] = jj[all][i], K[i] = kk[all][i], all = all ^ (1 << jj[all][i] - 1) ^ (1 << kk[all][i] - 1);
for (reg int i = 1; i <= n >> 1; ++i)
printf("%d %d\n", J[i], K[i]);