状压DP棋盘放置问题如何解决？
摘要：其实没什么好说的，就是在棋盘上的。 题目 P2915 [USACO08NOV] Mixed Up Cows G(混入的) 这个应该算是旅行商问题。 解法 状态定义: (dp_{i,state}) 表示选择状态为 (state)，以第
其实没什么好说的，就是在棋盘上的。
题目
P2915 [USACO08NOV] Mixed Up Cows G(混入的)
这个应该算是旅行商问题。
解法
状态定义:
\(dp_{i,state}\) 表示选择状态为 \(state\)，以第 \(i\) 头奶牛为结尾的方案数。
状态转移方程式
\[dp_{j,s|(1<<j)} = \sum dp_{i,s}
\]
哦对了！不要忘记了特殊条件！
相邻奶牛的编号之差均超过K
代码
戳我喵~
int a[17];
lint dp[17][(1 << 16) + 10];
int main() {
int n = re, k = re;
for (int i = 0; i < n; i++) a[i] = re;
for (int i = 0; i < n; i++) dp[i][1 << i] = 1;
for (int s = 0; s < (1 << n); s++) {
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) {
for (int j = 0; j < n; j++) {
if (!((s >> j) & 1) && abs(a[j] - a[i]) > k) {
dp[j][s | (1 << j)] += dp[i][s];
}
}
}
}
}
lint ans = 0;
for (int i = 0; i < n; i++) ans += dp[i][(1 << n) - 1];
wr(ans), endl;
}
P1879 [USACO06NOV] Corn Fields G
这题太经典了！
解法
先看数据范围：\(1 \le n,m \le 12\)
可以状压！
我们注意力惊人，发现了只有与它相邻的行与列才有关，所以我们考虑压缩一行的状态。
所以我们定义 \(dp_{i,j}\) 表示第 \(i\) 行，采用了第 \(j\) 个合法状态时的方案总数。
可是合法状态怎么统计呢？
我们可以在预处理阶段处理这合法状态。
合法状态即满足题目的条件，即不能有两块奶牛所在的草地相邻。
我们只需要判断 i & (i >> 1) 是否为 \(0\)，如果为 \(0\)，那么它就是中意的方案。
最后的 \(DP\) 还算简单，看代码就能理解。
状态转移方程式：
\[dp_{i,j} = \sum dp_{i - 1,k}
\]
代码
戳我喵
lint f[20], dp[20][(1 << 15) + 10]; //f是用来记录草地状态的
int n, m;
int main() {
IAKIOI;
n = re, m = re;
for (int i = 1; i <= n; i++) for (int j = 0, x; j < m; j++) {
x = re;
if (x) f[i] |= (1 << j);
}
vector<int> v;
for (int i = 0; i < (1 << m); i++) if ((i & (i >> 1)) == 0) v.push_back(i);
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < v.size(); j++) {
if ((v[j] & f[i]) == v[j]) {
for (int k = 0; k < v.size(); k++) {
if (!(v[j] & v[k])) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
}
}
}
}
}
lint ans = 0;
for (int i = 0; i < v.size(); i++) ans = (ans + dp[n][i]) % mod;
wr(ans), endl;
}
再来一个变式
P2704 [NOI2001] 炮兵阵地
这个其实就是可以覆盖的范围更大了嘛！
解法
参考T2
\(dp_{i,j,k}\) 表示第 \(i\) 行状态为 \(v_j\)，第 \(i - 1\) 行状态为 \(v_k\) 时的最大数量
把T2改一下就行了，在一行里，需要改条件(s & (s << 1)) == 0 且 (s & (s << 2)) == 0
代码
戳我喵~
int f[110], dp[101][701][701];
int n, m;
int main() {
n = re, m = re;
for (int i = 1; i <= n; i++) for (int j = 0; j < m; j++) {
char ch;
cin >> ch;
if (ch == 'P') f[i] |= (1 << j);
}
vector<int> v, cnt; //cnt表示的是此状态下的炮兵数量
for (int i = 0; i < (1 << m); i++) {
if ((i & (i >> 1)) == 0 && (i & (i >> 2)) == 0) {
v.push_back(i), cnt.push_back(__popcount(i));
}
}
dp[0][0][0] = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int x = 0; x < v.size(); x++) {
if ((v[x] & f[i]) == v[x]) {
for (int y = 0; y < v.size(); y++) {
if ((v[y] & f[i - 1]) == v[y]) {
for (int z = 0; z < v.size(); z++) {
if ((v[z] & f[i - 2]) == v[z] && !(v[x] & v[y]) && !(v[x] & v[z]) && !(v[z] & v[y])) {
dp[i][x][y] = max(dp[i][x][y], dp[i - 1][y][z] + cnt[x]); //取得是最大值，而不是方案数和
}
}
ans = max(ans, dp[i][x][y]);
}
}
}
}
wr(ans), endl;
}
练习题
P1896 [SCOI2005] 互不侵犯
P10449 费解的开关(可以用双向搜索)