目录
概述
如果我们有一张地图，要求是在符合某类条件的前提在地图上放置最优解，该怎么计算？
这也属于状压dp的应用之一。
相邻行递推
AcWing 237：
农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。
非常遗憾，部分土地是不育的，无法种植。
而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小，请你求出共有多少种种植方法。
土地上什么都不种也算一种方法。
输入格式
第 1 行包含两个整数 M 和 N。
第 2..M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。
输出格式
输出总种植方 1e8 取模后的值。
数据范围
1≤M,N≤12
输入样例：
2 3 1 1 1 0 1 0输出样例：
9
思路
之所以可以进行状压dp是因为列的数量较小，我们可以把一行压缩成一个整数。
也就是说我们有地图状态 g[i] = (10011)， 意味着第 i 行的第0、1、4列可以种植。
我们发现需要两个状态：当前行序号和当前行内种植的情况。
定义 dp[i][k]，表示[0, i] 行内且第 i 行状态为 k 的种植方案数，例如：
若 k = (10001)，意味着第 i 行的种植了第0、4列。
那么dp[i][k]可以从什么转移来呢？我们发现有以下约束：
- k 要服从地图的约束，也就是第 i 行的合法 k 仅能是 g[i] 的子集。
- k 内不含有相邻1，也就是行内需要合法。
- 第 i 行 k 也不能与 i - 1 行 k 不含有相邻1，也就是行间需要合法。
基于此，我们可以得知转移方程： dp[i][k] = dp[i - 1][t]。
其中，k、t 都行内合法且符合地图约束，且 k 与 t 行间兼容。
初始条件下，dp[0][服从地图0行的k] = 1。
算法过程
可以预处理出合法的 k。
行内合法的条件是： (k & (k >> 1) == 0。什么意思呢？k 的二进制位右移1位，与原来的 k 作与运算，就是试图让相邻的1重叠在一起，若真的有相邻的1，那么与运算结果必不为0。
为什么不用考虑左移呢？因为对于相邻的11，右1左移和左1右移是一样的。
如果你纠结于右移的溢出位的话，可以将二进制串前后补上无限长的0，再感受一下。
符合地图约束的k的条件：(k | g[i]) == g[i]。意味着k是g[i]的子集。
行间合法的条件是：(k1 & k2) == 0。意味着二者无重合的1，作为上下行时，就没有相邻的1。
那代码大概是这样的：
int solve(){
for (int k = 0; k <= mx; k++)
if (!(k & (k >> 1)))
st.push_back(k);
for (int k : st)
if ((k | g[0]) == g[0])
dp[0][k] = 1;
for (int i = 1; i < m; i++)
for (int k : st) if((k | g[i]) == g[i])
for (int pre_k : st) if (!(k & pre_k) && (pre_k | g[i - 1]) == g[i - 1])
dp[i][k] = (dp[i][k] + dp[i - 1][pre_k]) % MOD;
int ans = 0;
for (int k : st)
ans = (ans + dp[m - 1][k]) % MOD;
return ans;
}优化方案
空间优化
注意到dp[i]总是来自上一行dp[i - 1]，所以可以做一层空间优化。
仅使用两行储存dp，怎么区分哪行是上一行，哪行是这一行呢？
注意到枚举 i 时， i 的奇偶性持续发生变化，我们用 i & 1 作索引，dp[i & 1]储存第 i 行，dp[(i - 1) & 1] 就是上一行，当开始计算dp[i & 1][k]时，要先置 0 ，清除上上行的状态。
返回值优化
在最后，我们选择 i 多枚举1行，即计算到 i == m，此时答案就储存在 dp[m & 1][0]中，即 m 行，那个不存在的行，放置情况是0时即全空，这时的总状态。
Code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 13, MOD = 1e8;
int m, n, mx;
int g[N], dp[2][1 << N];
vector<int> st;
int solve(){
for (int k = 0; k <= mx; k++)
if (!(k & (k >> 1)))
st.push_back(k);
for (int k : st)
if ((k | g[0]) == g[0])
dp[0][k] = 1;
for (int i = 1; i <= m; i++)
for (int k : st) if((k | g[i]) == g[i]) {
dp[i & 1][k] = 0;
for (int pre_k : st) if (!(k & pre_k) && (pre_k | g[i - 1]) == g[i - 1])
dp[i & 1][k] = (dp[i & 1][k] + dp[(i - 1) & 1][pre_k]) % MOD;
}
return dp[m & 1][0];
}
int main(){
cin >> m >> n;
mx = (1 << n) - 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
int x; cin >> x;
g[i] |= x << j;
}
cout << solve();
return 0;
}复杂度
时间复杂度: O(
+
)
空间复杂度: O(
n：列数
m：行数
复杂度分析：
时间分析：{
枚举合法 k ，O()。
求合法 k 的数目：n 位不含有连续1的二进制数，设为 cnt(n)。
设 a[n] 表示 n 位不含有连续1且末位为1的二进制数数目，b[n] 表示 n 位不含有连续1且末位为0的二进制数数目。
则 cnt(n) = a[n] + b[n]。
其中 a[n] = b[n - 1]，b[n] = a[n - 1] + b[n - 1] = cnt(n - 1)。（前位为1则末位为0，前位为0则末尾任意）
则 cnt(n) = a[n] + b[n] = b[n - 1]+ a[n - 1] + b[n - 1] = cnt(n - 1) + b[n - 1] = cnt(n - 1) + cnt(n - 2)。
此乃斐波那契数列。考虑 cnt(1) = 2 = fib(3)，则 cnt(n) = fib(n + 2)。
fib(n)通项公式：
n趋于无穷大时，cnt(n) =
共有m行，每行枚举两遍k，忽略常数项，O()。
总时间复杂度 O( +
)。
}
相邻两行递推
AcWing 327：
司令部的将军们打算在 N×M 的网格地图上部署他们的炮兵部队。
一个 N×M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用
H表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个由空格分割开的正整数，分别表示 N 和 M；
接下来的 NN 行，每一行含有连续的 M 个字符(
P或者H)，中间没有空格。按顺序表示地图中每一行的数据。输出格式
仅一行，包含一个整数 K，表示最多能摆放的炮兵部队的数量。
数据范围
N≤100,M≤10
输入样例：
5 4 PHPP PPHH PPPP PHPP PHHP输出样例：
6
这次变成了两行递推。
思路
只需要对上次的代码稍作修改。
dp[i & 1][k1][k2] 表示 [0, i] 行且第 i 行状态为 k1，第 i - 1 行状态为 k2 的最值。
三个约束：
- k 要服从地图的约束，也就是第 i 行的合法 k 仅能是 g[i] 的子集。
- k 内不含有相邻1或相间一个0，也就是行内需要合法。
- 第 i 行 k 也不能与 i - 1 行和 i - 2k 不含有相邻1，也就是两行间需要合法。
算法过程
行内合法的条件是： (k & (k >> 1) == 0 && (k & (k >> 2) == 0。
符合地图约束的k的条件：(k | g[i]) == g[i]。
行间合法的条件是：(k1 & k2) == 0 && (k1 & k3) == 0 && (k2 & k3) == 0 。
Code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 10, MOD = 1e8;
int m, n, mx;
int g[N], dp[2][1 << M][1 << M], cnt[1 << M];
vector<int> st;
bool check(int k){
return !(k & (k >> 1)) && !(k & (k >> 2));
}
bool check(int a, int b){
return !(a & b);
}
int solve(){
for (int k = 0; k <= mx; k++)
if (check(k)) {
st.push_back(k);
cnt[k] = bitset<M>(k).count();
}
for (int k1 : st) if ((k1 | g[0])== g[0]) {
dp[0][k1][0] = cnt[k1];
for (int k2 : st) if ((k2 | g[1])== g[1] && check(k1, k2))
dp[1][k2][k1] = cnt[k1] + cnt[k2];
}
for (int i = 2; i <= n + 1; i++)
for (int k1 : st) if ((k1 | g[i]) == g[i])
for (int k2 : st) if ((k2 | g[i - 1]) == g[i - 1] && check(k1, k2)) {
dp[i & 1][k1][k2] = 0;
for (int k3 : st) if ((k3 | g[i - 2]) == g[i - 2] && check(k1, k3) && check(k2, k3))
dp[i & 1][k1][k2] = max(dp[i & 1][k1][k2], dp[(i - 1) & 1][k2][k3] + cnt[k1]);
}
return dp[(n + 1) & 1][0][0];
}
int main(){
cin >> n >> m;
mx = (1 << m) - 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
char x; cin >> x;
g[i] |= ((x == 'P') << j);
}
cout << solve();
return 0;
}复杂度
时间复杂度: O(
)
空间复杂度: O(
T：常数，1 < T <
n：列数
m：行数
特殊优化：编译期计算
以第一题为例，我们知道 k 可以预处理得到，那能否更进步一些呢？
C++提供大量的静态计算支持，我们可以利用C++特性做一些工作。
我们直接在编译期计算 k 的合法状态，constexpr 函数会尝试进行编译期计算，我们传入编译期常量 N，就会在编译期直接生成出合法状态的数组。
虽然表面上我们是在编译期调用计算函数，但其实它已经算好了，已经储存在可执行程序中，这就省去了一个O()。
运行期由于每次数据范围不同，可以二分得到 k 的上界，然后正常计算即可。
constexpr int N = 13, MOD = 1e8;
int m, n, mx;
int g[N], dp[2][1 << N];
constexpr pair<array<int, 1 << N>, int> get_st(int MX){
array<int, 1 << N> st{};
int st_size = 0;
for (int k = 0; k < MX; k++)
if (!(k & (k >> 1)))
st[st_size++] = k;
return {st, st_size};
}
constexpr auto s = get_st(1 << N);
constexpr auto st = s.first;
constexpr auto st_size = s.second;
int solve(){
int upper = upper_bound(st.begin(), st.begin() + st_size, mx) - st.begin();
for (int k = 0; k < upper; k++)
if ((st[k] | g[0]) == g[0])
dp[0][st[k]] = 1;
for (int i = 1; i <= m; i++)
for (int k = 0; k < upper; k++) {
dp[i & 1][st[k]] = 0;
for (int pre_k = 0; pre_k < upper; pre_k++)
if (!(st[k] & st[pre_k]) && (st[k] | g[i]) == g[i])
dp[i & 1][st[k]] = (dp[i & 1][st[k]] + dp[(i - 1) & 1][st[pre_k]]) % MOD;
}
return dp[m & 1][0];
}总结
这就是状压DP的又一实例：网格图递推，后续将讲解利用状压DP的更复杂度的递推类问题。