状压dp

# 状压dp ## 定义 状态压缩动态规划，简称**状压dp**，通过二进制**将状态压缩为整数**来达到优化转移的目的 ### 什么时候用呢 当你看到类似的数据范围，并且长的就像 $dp$ 的题，一般就可以用 ## 一个简单的例子 对于一个01背包（大家都会对吧） 有 $n\leq 15$ 件物品和一个容量无限大的背包，第 $i$ 件物品所占空间为 $w_i$ ，价值为 $v_i$ ，求每种放法的价值和占用的空间 ### 1.定义状态 我们要求每种放法的价值，且对于一个01背包的每个物品都只有放与不放两种情况 于是我们定义的状态应是**这 $n$ 件物品放与不放的情况** 容易想到我们可以开个 $n$ 维数组，第 $i$ 个维度的下标如果是 $1$ 则代表放第 $i$ 件物品， 反之则不放 > 假设我们有 $5$ 件物品， 那么 $dp[1][0][1][1][0]$ 则代表放第 $1,3,4$ 件物品可以获得的价值 但你愿意一个维度一个维度地开吗？（） 我们发现对于这个问题可以用**二进制**来表示所有情况，如果我们将其**转化为十进制**就可以用 $1$ 个维度来表达刚才 $n$ 个维度所表达的信息 例如刚才我们显然可以用 $00000\thicksim 11111$ 来表示所有情况，转化为十进制就是 $0\thicksim (1<<5-1)$ ### 2.如何转移 放的状态只能由不放的状态转移而来 例如$dp[10000_{(2)}]=dp[00000_{(2)}]+v[1]$，$dp[11000_{(2)}]=dp[10000_{(2)}]+v[2]=dp[01000_{(2)}]+v[1]$ ### 3.代码 ~~~c++ #include<cstdio> int dp[2][(1 << 15) + 5]; //dp[0]为价值,dp[1]为空间 int n, w[20], v[20]; void print(int s); int main() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d%d", &w[i], &v[i]); for(int i = 0; i < (1 << n); ++i) { for(int j = 0; j < n; ++j) { if(!(i & (1 << j))) { dp[0][i | (1 << j)] = dp[0][i] + v[j]; dp[1][i | (1 << j)] = dp[1][i] + w[j]; } } } for(int i = 0; i < (1 << n); ++i) { print(i); printf("\t%d\t%d\n", dp[0][i], dp[1][i]); } return 0; } void print(int s) { if(!s) printf("0"); for(int k = 0; (1 << k) <= s; ++k) { if(s & (1 << k)) printf("1"); else printf("0"); } } /* 3 2 5 3 8 4 9 */ //一组样例 /* 0 0 0 1 5 2 01 8 3 11 13 5 001 9 4 101 14 6 011 17 7 111 22 9 */ ~~~ ## 互不侵犯 在 $N\times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案？ 国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子 ### solution 我们定义 $dp[i][j][l]$ 表示前 $i$ 行，第 $i$ 行的状态为 $j$ ，且棋盘上已经放了 $l$ 个国王时的合法方案数 对于每个状态 $j$ ，其二进制位上为 $1$ 则代表那个位上放置国王，反之则不放 例如下图 $j=101001_{(2)}$ ，$bitcount(j)=3$  设当前行状态为 $j$ ，上一行状态为 $k$ ，在**保证当前行和上一行不冲突**的前提下，枚举所有可能的 $k$ 进行转移，有转移方程 $$ f[i][j][l]=\sum f[i-1][k][l-bitcount(j)] $$ ### 代码 ```c++ #include<cstdio> int n, p; long long dp[11][(1 << 9) + 5][101], ans; int bitcount[(1 << 9) + 5]; int main() { scanf("%d%d", &n, &p); dp[0][0][0] = 1; for(int i = 0; i < (1 << n); ++i) { int t = i; while(t) { if(t & 1) ++bitcount[i]; t >>= 1; } } for(int i = 1; i <= n; ++i) { for(int j = 0; j < (1 << n); ++j) { if(!(j & (j << 1))) { for(int k = 0; k < (1 << n); ++k) { if(!((j & (k | k << 1 | k >> 1)) || (k & (k << 1)))) { for(int l = bitcount[k] + bitcount[j]; l <= p; ++l) { dp[i][j][l] += dp[i - 1][k][l - bitcount[j]]; } } } } } } for(int i = 0; i < (1 << n); ++i) ans += dp[n][i][p]; printf("%lld\n", ans); return 0; } ``` ## 炮兵阵地 司令部的将军们打算在 $N\times M$ 的网格地图上部署他们的炮兵部队。 一个 $N\times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用 $\texttt{H}$ 表示），也可能是平原（用 $\texttt{P}$ 表示），如下图。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：  如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 ### solution 我们定义 $dp[l][s][i]$ 表示上一行状态为 $l$，当前行状态为 $s$，当前考虑到第 $i$ 行时最多放置的炮兵数，$bin[i]$ 表示第 $i$ 行的地形情况 然后我们发现对于每一行 $i$，只需要 $i,i-1,i-2$ 三行，于是考虑使用滚动数组进行优化（否则$MLE\ \ 0$） 与互不侵犯相同，对于每个状态 $l$（或 $s$），二进制位上为 $1$ 则代表放置炮兵，反之不放 设上上行状态为 $j$ ，在**满足题目要求**的前提下，有转移方程 $$ dp[l][s][i]=max(dp[j][l][i-1])+bitcount(s) $$ ### 代码 ```c++ #include<cstdio> int dp[(1 << 10) + 5][(1 << 10) + 5][3], bin[105], bitcount[(1 << 10) + 5]; int n, m, ans; inline int max(const int &a, const int &b) {return a > b ? a : b;} int main() { scanf("%d%d", &n, &m); for(int i = 0; i < (1 << m); ++i) { int t = i; while(t) { if(t & 1) ++bitcount[i]; t >>= 1; } } for(int i = 0, x; i < n; ++i) { for(int j = 0; j < m; ++j) { scanf(" %c", &x); if(n == 1 && m == 1 && x == 'P') { printf("1\n"); return 0; } bin[i] = (bin[i] << 1) | x == 'H'; } } for(int l = 0; l < (1 << m); ++l) { for(int s = 0; s < (1 << m); ++s) { if(!((l & (s | bin[0] | (l << 1) | (l << 2))) || (s & (bin[1] | (s << 1) | (s << 2))))) { dp[l][s][1] = bitcount[s] + bitcount[l]; } } } for(int i = 2; i < n; ++i) { for(int l = 0; l < (1 << m); ++l) { if(!(l & (bin[i - 1] | (l << 1) | (l << 2)))) { for(int s = 0; s < (1 << m); ++s) { if(!(s & (bin[i] | (s << 1) | (s << 2) | l))) { for(int j = 0; j < (1 << m); ++j) { if(!(j & (bin[i - 2] | (j << 1) | (j << 2) | s | l))) { dp[l][s][i % 3] = max(dp[l][s][i % 3], dp[j][l][(i - 1) % 3] + bitcount[s]); } } } } } } } for(int l = 0; l < (1 << m); ++l) { for(int s = 0; s < (1 << m); ++s) { ans = max(ans, dp[l][s][(n - 1) % 3]); } } printf("%d\n", ans); return 0; } ``` ## 玉米田 农场主John新买了一块长方形的新牧场，这块牧场被划分成 $M$ 行 $N$ 列($1 ≤ M ≤ 12; 1 ≤ N ≤ 12$)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。 遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。 John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案） ### solution 相信你已经找到套路了对吧（确信 我们定义 $dp[i][j]$ 表示前 $i$ 行且第 $i$ 行状态为 $j$ 的方案数，$bin[i]$ 第 $i$ 行的地形情况 （熟悉吗） 与前面同样的，对于每个状态 $j$ ，二进制位上为 $1$ 则代表种草，反之不种 仍然同样的，设当前行状态为 $j$ ，上一行状态为 $k$ ，在**满足题目要求**的前提下，有转移方程 $$ dp[i][j]=\sum dp[i-1][k] $$ ### 代码 ```c++ #include<cstdio> const int MOD = 100000000; int dp[15][(1 << 12) + 5], bin[15]; int n, m, ans; int main() { scanf("%d%d", &n, &m); for(int i = 0, x; i < n; ++i) { for(int j = 0; j < m; ++j) { scanf("%d", &x); bin[i] = (bin[i] << 1) | !x; } } for(int i = 0; i < (1 << m); ++i) { if(!(i & (bin[0] | (i << 1)))) { dp[0][i] = 1; } } for(int i = 1; i < n; ++i) { for(int j = 0; j < (1 << m); ++j) { if(!(j & (bin[i] | (j << 1)))) { for(int k = 0; k < (1 << m); ++k) { if(!(k & (bin[i - 1] | (k << 1) | j))) { dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD; } } } } } for(int i = 0; i < (1 << m); ++i) { ans = (ans + dp[n - 1][i]) % MOD; } printf("%d\n", ans); } ``` ## 习题 [P1896 互不侵犯](https://www.luogu.com.cn/problem/P1896) [P2704 炮兵阵地](https://www.luogu.com.cn/problem/P2704) [P1879 Corn Fields G](https://www.luogu.com.cn/problem/P1879) [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694) [P2831 愤怒的小鸟](https://www.luogu.com.cn/problem/P2831)