状压DP如何记录方案 / 路径 / ...
  • 板块学术版
  • 楼主Starlight237
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/8/24 21:46
  • 上次更新2023/11/6 19:28:38
查看原帖
状压DP如何记录方案 / 路径 / ...
75765
Starlight237楼主2020/8/24 21:46

比如月赛 div1 B subtask2,我原用状压 DP 来写,但记录路径的地方写挂了,只好换成 DFS 水了 subtask2 的分。

能简述一下这种题目状压 DP 怎么记录方案吗?

我的思路:每次记录使状态 SS 达到最优解的最后一步,然后再按照该方案迭代,最后倒序输出。

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]);
2020/8/24 21:46
加载中...