摆放类状压DP基础题

P1879 [USACO06NOV] Corn Fields G

有一块 \(n \times m(n,m \le 12)\) 的网格地， 每个格子用 \(0\) 或 \(1\) 代表是否这个区域是否肥沃。只有肥沃的地块才能种草，但不能将草种在相邻的两个格子中，求出一共有多少种符合要求的种草方案（可以全不种），答案对 \(10^8\) 取模。

考虑将每一行的种草情况压成一个二进制状态。对于每一行，枚举所有 \(2^m\) 种方案。由于不肥沃的地方不能种草，所以先与该行的肥沃情况的状压变量按位取与。例如，设当前枚举到的状态为 \(i\)，该行的肥沃情况是 \(r\)，对应的方案为 \(t=i\land r\)：

\[i=(\textcolor{red}{1}01\textcolor{red}{1}00)_2 \\ r=(\textcolor{red}{1}10\textcolor{red}{1}10)_2 \\ t=(\textcolor{blue}100\textcolor{blue}100)_2 \]

接下来我们要判断是否有相邻格子都种了草。对于左右相邻，我们只需将状态全都左移一位，然后再与原来的状态按位取与。如果答案为 \(0\) 则说明没有相邻，否则有相邻。例如下面的 \(t=(101001)_2\) 就是一个合法的方案：

\[\begin{align} t&=(0101001)_2\\ t\ll1&=(1010010)_2\\ t \land(t\ll1)&=(0000000)_2 \end{align} \]

而 \(t=(101100)_2\) 就是不合法的：

\[\begin{align} t&=(010\textcolor{red}1100)_2\\ t \ll 1&=(101\textcolor{red}1000)_2\\ t \land(t\ll1)&=(000\textcolor{red}1000)_2 \end{align} \]

左右相邻考虑完了，接下来考虑上下相邻。显然为了达到这一目标，我们在搜索的时候要记录上一行的状态 \(pre\)。检查当前方案中是否存在与上一行相邻的草块，只需要用这一行的状态跟上一行的状态按位取与。同样地，如果结果为 \(0\) 则说明没有相邻，否则有相邻。这个比较显然，就不用举例子了。

现在我们已经可以判断方案是否合法，但还存在一个问题：可能存在重复的方案。例如当 \(r=(110110)_2\) 时，枚举到 \(i=(100110)_2\) 或 \((101110)_2\) 得到的状态是相同的 \(t=(100110)_2\)。因此我们还需要一个标记数组 \(vis\) 来判断是否重复。

时间复杂度：\(O(nm+2^{n+m})\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 13, MOD = 1e8;
inline int read(){int x = 0, neg = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') neg = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * neg;
}
int n, m, a[N];
ll dp[N][1 << N];
ll dfs(int u, int pre){if (u == n + 1) return 1;if (dp[u][pre] != -1) return dp[u][pre];bool vis[1 << N] = {0};ll res = 0;for (int i = 0; i < (1 << m); ++i) {int t = i & a[u];if (t & (t << 1) || t & pre || vis[t]) continue ;res = (res + dfs(u + 1, t)) % MOD;vis[t] = 1;}return dp[u][pre] = res;
}
int main() {n = read(), m = read();for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++) a[i] = (a[i] << 1) | read();memset(dp, -1, sizeof(dp));printf("%lld", dfs(1, 0));return 0;
}

P1896 [SCOI2005] 互不侵犯

在 \(N\times N(N \le 9)\) 的棋盘里面放 \(K\) 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到与它 \(8\) 邻接的位置。

跟上一题类似，用一个状压变量来表示每一行棋子的摆放情况，不同的是上一题要求摆放位置 \(4\) 邻接范围内不相邻，而这一题要求 \(8\) 邻接位置内不相邻，只需要多判断 \(t \land (pre \ll 1)\) 和 \(t \land (pre \gg 1)\) 即可。同时，题目还限制了棋子的个数，所以我们还需要多开一维表示棋子的个数，当前行内的棋子个数不得超过限制。只需要统计状压变量中 \(1\) 的个数即可。

时间复杂度 \(O(4^NN)\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10;
inline int read(){int x = 0, neg = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') neg = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * neg;
}
int popcount(int x){int res = 0;while(x) res += x & 1, x >>= 1;return res;
}
bool check(int now, int pre){return now & (now << 1) || now & pre || (now & (pre << 1)) || (now & (pre >> 1));
}
int n, m;
ll dp[N][N * N][1 << N];
ll dfs(int step, int k, int pre){if(step == n + 1 && k) return 0;if (k == 0) return 1;if (dp[step][k][pre] != -1) return dp[step][k][pre];ll res = 0;for(int i = 0; i < (1 << n); i++){int cnt = popcount(i);if(cnt > k || check(i, pre)) continue;res += dfs(step + 1, k - cnt, i);}return dp[step][k][pre] = res;
}
int main() {n = read(), m = read();memset(dp, -1, sizeof(dp));printf("%lld", dfs(1, m, 0));return 0;
}

P2704 [NOI2001] 炮兵阵地

给定 \(n\times m(n \le 100,m \le 10)\) 的字符网格，H代表山地，P代表平原，炮兵部队只能部署在平原上。炮兵部队的攻击范围是：沿横向左右各两格，沿纵向上下各两格。在每个炮兵部队的攻击范围不重叠的情况下，求出可部署炮兵部队数量的最大值。

仍然和前两题是类似的，只不过这回我们摆放的东西向前跨了两行，所以我们需要存两个状压变量。然而，因为有两个状压变量，所以我们的 \(\text{dp}\) 数组也需要增开一维，我们应该考虑一下空间问题。按照之前的思路，我们应该开int dp[n][2^m][2^m]，耗费的空间为 \(4\text{ B} \times100\times 2^{10}\times 2^{10}= 400\text{ MB}\)，而原题的空间限制是 \(128\text{ MB}\)，需要优化。观察到每一行状态的判断只关系到前两行，因此可以考虑滚动优化。然而滚动优化后无法打记忆化搜索，所以我们就只能打常规的迭代 \(\text{DP}\) 了。

设 \(\text{dp}_{i,j,k}\) 表示当前考虑到第 \(i\) 行，状态为 \(j\)，前一行的状态为 \(k\) 的答案，则转移方程易得：

\[\text{dp}_{i,j,k}=\max\{\text{dp}_{i,j,k},\text{dp}_{i-1,k,l}\} \\ j,k,l\in[0,2^m) \]

设 \(now,last\) 分别为当前行和前一行，然后进行滚动优化：

\[\text{dp}_{now,j,k}=\max\{\text{dp}_{now,j,k},\text{dp}_{last,k,l}\} \\ j,k,l\in[0,2^m)\\now,last\in\{0,1\},now \oplus last=1 \]

每完成一行，就交换 \(now,last\) 来实现滚动。这样，就只需要 \(4\text{ B} \times 2 \times 2^{10} \times2^{10}=8 \text{ MB}\) 的空间了。

#include<bits/stdc++.h>
using namespace std;
const int N = 105, M = 10;
inline int read(){int x = 0, neg = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') neg = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * neg;
}
int n, m, a[N], cnt[1 << M], ans, now = 0, last = 1; //cnt[i]=popcount(i)
char g[N][M];
int dp[2][1 << M][1 << M];
bool check(int x, int i){return (x & a[i] || x & (x << 1) || x & (x << 2));} //第i行摆放状态为x是否非法
int main() {n = read(), m = read();for(int i = 1; i <= n; i++) {scanf("%s", g[i]);for(int j = 0; j < m; j++) a[i] <<= 1, a[i] |= g[i][j] == 'H';}for(int i = 0; i < (1 << m); i++){int x = i;while(x) cnt[i] += x & 1, x >>= 1;}for(int i = 1; i <= n; i++) {for(int j = 0; j < (1 << m); j++){if(check(j, i)) continue;for(int k = 0; k < (1 << m); k++){if((i >= 2 && check(k, i - 1)) || j & k) continue;for(int l = 0; l < (1 << m); l++){if((i >= 3 && check(l, i - 2)) || j & l) continue;dp[now][j][k] = max(dp[now][j][k], cnt[j] + dp[last][k][l]);}if(i == n) ans = max(ans, dp[now][j][k]);}}swap(now, last);}printf("%d", ans);return 0;
}