引入
先看一道例题：（可能 r18）
有 \(N\) 个男生和 \(N\) 个女生。小 A 喜欢磕 CP，现在小 A 想要磕 \(N\) 对 CP。不过每一个人都有自己的 npy，也不是随随便便就能磕成一对。现在小 A 找到了你，要你求出有多少种磕 CP 的方式。
我们显然可以暴力枚举每一个男生跟谁组 CP 然后判断是否合法。但是这方法 \(O(N!)\)，在 \(N = 20\) 的情况下显然不可通过。
我们可以设计出一个 pure and simple 的状态：\((i, 0/1, 0/1, ......, 0/1)\)（其中共有 \(N\) 个 \(0/1\)），表示目前配对了 \(i\) 个男生，女生是否被配对过。
转移不难想：只要第 \(i + 1\) 个男生愿意与某个没有配对的女生磕 CP，就可以转移。
但是，你还要写 \(20\) 个 if 用于输出答案（或许不用？），谁想啊......
考虑到 \(2^{20} - 1\)int 存的下，所以尝试将之前二十个维度压成一个维度。
此即“状态压缩”dp，简称 状压 dp。
状压 dp 常见套路
可行性问题转换最优化问题
Moovie Mooving G
奶牛 Bessie 想连续看 \(L (1 \le L \le 10^8)\) 分钟的电影，有 \(N (1 \le N \le 20)\) 部电影可供选择，每部电影会在一天的不同时段放映。
Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。
请帮 Bessie 计算她能够做到从 \(0\) 到 \(L\) 分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。
很显然，直接做似乎不行了......
我们发现，只要某个方案能够耗掉 \(L\) 分钟，就可以了。所以我们对于一个要观看的电影集合，只保留这些电影最长能耗多少时间。
最小化背包数量
有 \(\infty\) 个容量为 \(W\) 的背包，还有 \(N\) 个体积为 \(W_1, W_2, \cdots, W_N\) 的物品。
现在我们要将这些物品放进某些背包满足没有背包超载。求最少有多少个背包里面有物品。
Naive
定义 \(dp_{state}\) 为只考虑 \(state\) 里面的元素所需要的最小背包数量。
枚举开一个新背包里面装某些东西。
枚举原先集合 \(O(2^N)\)，每一个原先集合有 \(2^N\) 种转移，总共 \(O(2^{(2N)}) = O(4^N)\)。
Improvment 1
考虑到我们只需要对没放的东西新开一个背包。
所以仅需枚举剩下东西的子集。
时间复杂度 \(O(3^N)\)，证明如下：
考虑选了正好 \(i\) 个物品对时间复杂度的贡献。
\[\sum \limits_{i = 0}^N \binom{N}{i}2^{N - i} \]\[= \sum \limits_{i = 0}^N \binom{N}{i}1^i2^{N - i} \]\[= (1 + 2)^N = 3^N \]Improvment 2
其实我们只需要枚举下一个要放什么元素，然后转移即可。
时间复杂度纯粹的 \(O(N2^N)\)。
按行 dp
有 \(N \cdot M\) 的网格，每个网格内包含 "0", "1", 或 "?" 。每个 "?" 会被等概率替换为 "0" 或 "1" 。请计算网格图中不存在两个相邻网格均为 "1" 的 概率。 本题中我们认为网格 \((i,j)\) 与网格 \((i + 1, j), (i − 1, j), (i, j + 1), (i, j − 1)\) 相邻 。答案对 \(998244353\) 取模。
我们定义 \(dp_{i, state}\) 为当前在第 \(i\) 行，第 \(i\) 行状态为 \(state\) 的方案数。
Naive
直接枚举当前行和之前行，校验。
\(O(N4^MM^2)\)。
Inprovment 1
这一行的 1 上一行不会有，枚举子集。
\(O(N3^MM^2)\)。
Improvment 2
校验的环节可以 \(O(N2^M)\) 预处理。
总时间复杂度 \(O(N3^M)\)。
Code:
#include <bits/stdc++.h>
using namespace std;
const int kMod = 998244353;
int n, m, dp[16][1 << 16], cnt, sm, cz[16][1 << 16];
char c[22][22];
bool check(int x, int y) {
for(int j = 0; j < m; j++) {
//cout << c[x][j]
if((((y >> j) & 1) && c[x][j] == '0') || (!((y >> j) & 1) && c[x][j] == '1')) {
return 0;
}
}
return !(y & (y >> 1));
}
bool check2(int x, int y) {
for(int j = 0; j < m; j++) {
if(((x >> j) & 1) && ((y >> j) & 1)) {
return 0;
}
}
return 1;
}
int qpow(int x, int y) {
int ans = 1;
for(; y; y >>= 1) {
if(y & 1) {
ans = 1ll * ans * x % kMod;
}
x = 1ll * x * x % kMod;
}
return ans;
}
int qinv(int x) {
return qpow(x, kMod - 2);
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < m; j++) {
cin >> c[i][j];
cnt += c[i][j] == '?';
}
}
dp[0][0] = 1;
int tmp = 0;
//cout << check(1, 0) << '\n';
for(int i = 1; i <= n; i++) {
for(int j = 0; j < (1 << m); j++) {
cz[i][j] = check(i, j);
}
}
cz[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < (1 << m); j++) {
if(cz[i][j]) {
for(int k = (1 << m) - 1 - j; ; k = (k - 1) & ((1 << m) - 1 - j)) {
//cout << i << ' ' << j << ' ' << k << '\n';
if(cz[i - 1][k]) {
//cout << i << ' ' << k << '\n';
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % kMod;
}
if(!k) {
break;
}
}
}
if(i == n) {
tmp = (tmp + dp[i][j]) % kMod;
}
//cout << dp[i][j] << ' ';
}
//cout << '\n';
}
cout << 1ll * tmp * qinv(qpow(2, cnt)) % kMod << '\n';
return 0;
}
（CodeBlocks 炸了，所以没有换行）
利用转移的特殊性状压转移
一排 \(N\) 个玩家，第 \(i\) 名玩家有一个战力值 \(A_i\)。当满足以下全部条件时，玩家 \(i\) 和玩家 \(j\) 可以组队：
-
\(A_i\) 与 \(A_j\) 互质；
-
\(|i - j| \le K\)。
请问你至多可以组出几只二人队伍。每个玩家不能加入超过一个队伍。
注意到 \(K\) 只有 \(8\)。
直接状压 \(i\) 到 \(i - k + 1\)（\(i - k\) 无需维护）的配对情况，状压转移。
\(A_i\) 与 \(A_j\) 互质的条件可以预处理。
不过这题实现起来超级恶心，所以我放一个代码用来查错：
//cout << dp[n][j] << ' ';
#include <bits/stdc++.h>
using namespace std;
int n, k, arr[100010], dp[100010][1 << 8], xg[100010][10];
int gcd(int x, int y) {
return !y? x : gcd(y, x % y);
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
for(int j = 1; j <= min(i - 1, k); j++) {
xg[i][j] = gcd(arr[i], arr[i - j]) == 1;
}
}
// 这里写了扩散
for(int i = 1; i <= n; i++) {
for(int j = 0; j < (1 << min(k, i)); j++) { // i 可以小于 K
int tmp = (j << 1) & ((1 << k) - 1);
dp[i + 1][tmp] = max(dp[i + 1][tmp], dp[i][j]);
for(int x = 1; x <= min(i, k); x++) {
if(!((j >> (x - 1)) & 1) && xg[i + 1][x]) { // 还可以配对
dp[i + 1][(tmp | (1 << x) | 1) & ((1 << k) - 1)] = max(dp[i + 1][(tmp | (1 << x) | 1) & ((1 << k) - 1)], dp[i][j] + 1); // 注意这里 & ((1 << k) - 1)，否则 WA
}
}
}
}
int ans = 0;
for(int j = 0; j < (1 << min(k, n)); j++) { // N 可以小于 K
ans = max(ans, dp[n][j]);
//cout << dp[n][j] << ' ';
}
cout << ans << '\n';
return 0;
}
祝大家 for(;;) rp += INT_MAX;！