状压 DP
学习状压 dp 之前,请确认你已经完成了 动态规划基础 部分内容的学习。
(同时建议学习 位运算 部分的内容)
状压 DP 简介¶
状压 dp 是动态规划的一种,通过将状态压缩为整数来达到优化转移的目的。
例题¶
「SCOI2005」互不侵犯
在
我们用
其中
我们需要在刚开始的时候预处理出一行的所有合法状态
设当前行的状态为
需要注意在转移时排除相邻两行国王互相攻击的不合法情况。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;
void dfs(int x, int num, int cur) {
if (cur >= n) { // 有新的合法状态
sit[++cnt] = x;
sta[cnt] = num;
return;
}
dfs(x, num, cur + 1); // cur位置不放国王
dfs(x + (1 << cur), num + 1,
cur + 2); // cur位置放国王,与它相邻的位置不能再放国王
}
int main() {
cin >> n >> k;
dfs(0, 0, 0); // 先预处理一行的所有合法状态
for (int i = 1; i <= cnt; i++) f[1][i][sta[i]] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= cnt; j++)
for (int l = 1; l <= cnt; l++) {
if (sit[j] & sit[l]) continue;
if ((sit[j] << 1) & sit[l]) continue;
if (sit[j] & (sit[l] << 1)) continue;
// 排除不合法转移
for (int p = sta[j]; p <= k; p++) f[i][j][p] += f[i - 1][l][p - sta[j]];
}
long long ans = 0;
for (int i = 1; i <= cnt; i++) ans += f[n][i][k]; // 累加答案
cout << ans << endl;
return 0;
}
|
习题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用