第十七章 状态压缩动态规划
对于 “状态压缩动态规划” 中的状态，通常与集合相关联。集合本身有三个性质：确定性，互异性和无序性。这也就决定了只关心每个元素的存在状态，而这通常可以使用 $0$ 或者 $1$ 表示存在或者不存在。
由此可见，可以通过一串 $01$ 码来清晰地表示一个集合的状态。同时，在确定了最低位的前提下，一串 $0-1$ 码和一个二进制数一一对应。这种表示状态的方式被称为状态压缩，简称状压。所谓 “压缩”，即是用一个二进制数来保存一组状态，将一个集合的状态压缩进了一个二进制数中，而通常这个二进制数在十进制下可以作为其编号。状态压缩本质上是进行了两步操作：
- 给这个集合的每个状态一个编号；
- 通过该编号，轻易地访问该状态。
状态压缩是什么
例1：P1896 [SCOI2005] 互不侵犯
通过观察性质，不难发现按一定顺序。因此，设计状态时可以当前行、上一行的状态都记录下来。使用 $0$ 或者 $1$ 来表示某一行的状态，考虑使用二进制数来表示。
此时需要注意，一般情况下状压之后，状态中的每一位都是倒着存的，因为这符合二进制的定义规则。可以类比，从左至右列标逐渐增大，但是二进制位从左到右权值逐渐减小。
这种访问方式可以实现比数组寻址更快速、但同样准确的访问。比如 (1 << (k - 1)) & s 可以访问状态 $s$ 的第 $k$ 位上是 $1$ 还是 $0$。而 (j >> k) << k 则可以把状态 $j$ 的二进制位表示下最右边几位清零，而数组不能以 $\mathcal O(1)$ 的复杂度直接清零。
考虑用 $f_{i, j, k}$ 表示前 $i$ 行，第 $i$ 行的状态的二进制表示（十进制下的值）为 $j$，放置了 $k$ 个国王的方案数，那么状态转移方程就是：
\[f_{i, j, k} = \sum f_{i - 1, new, k - popcount(j)}\]其中 $new$ 表示所枚举的上一行的所有合法状态，因为所定义的 $1$ 即为放了国王。最终复杂度是 $\mathcal O(4^n \time nk)$。其中有许多需要统计的数据是可以预处理来进行优化效率的。
int lenbit(lxl x) {
int ret = 0;
while (x) {
if (x & 1) ret++;
x >>= 1;
}
return ret;
}
bool check(lxl x, lxl y) {
if (x & y) return false;
if ((x << 1) & y) return false;
if ((x >> 1) & y) return false;
if ((x >> 1) & x) return false;
if ((y >> 1) & y) return false;
return true;
}
F[0][0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < (1 << N); j++) {
int lj = lenbit(j);
for (int k = 0; k <= K; k++) {
if (lj > k) continue;
for (int l = 0; l <= (1 << N) - 1; l++) {
if (!check(j, l)) continue;
F[i][j][k] += F[i - 1][l][k - lj];
}
}
}
}
for (int i = 0; i < (1 << N); i++) ans += F[N][i][K];
例2：P2622 关灯问题II
需要注意的是状压类的题目，最终的时间复杂度表达式里都会有一个 $\mathcal O(2^k)$ 的因子。
可以发现，当 $k \ge 20$ 的时候 $2^k$ 也已经高于 $10^6$。而随着 $k$ 到达 $24$，$2^k$ 更是突破了 $10^7$，已经是 $1s$ 内常数较大时能达到的极限。所以这就启示：如果可以状压，那么一定存在一个量，该量的范围比较小。
发现 $n \le 10$，那么某一个时刻全部灯的状态，便可以用一个小于 $2^10 = 1024$ 的自然数记录下来。同时需要注意到本题一个重要的性质：转移时是按照次序的。考虑十进制下，$0 \sim 2^n - 1$ 中每个数都表示一个状态，而这个数越大，越靠近最终所需的状态，即全部灯都打开时都状态。
因此可以考虑从 $0$ 开始不断往上枚举，遍历 $m$ 个控制效果。设当前状态时 $i$，通过某个控制效果 $z_j (j = 1, 2, 3, \cdots, m)$ 可以变成状态 $t$，那么设 $f_s$ 表示到达状态 $s$ 时所需的最小步数，就有转移：
\[f_t = \min_{z_j(i) = t} \\{ f_i \\} + 1\]其中 $z_j(i)$ 表示对状态 $i$ 使用了 $z_j$ 的控制效果。
std::fill(f + 1, f + (1 << maxN), inf);
for (int i = 0; i < (1 << n); i++) {
for (int j = 1; j <= m; j++) {
int t = i;
for (int k = 1; k <= n; k++) {
if ((a[j][k] == 1 && !((1 << (k - 1)) & i)) ||
(a[j][k] == -1 && ((1 << (k - 1)) & i))) {
t ^= (1 << (k - 1));
}
}
f[t] = std::min(f[t], f[i] + 1);
}
}
状态压缩的一般技巧
例3：CF11D A Simple Task
通过观察数据范围可知，或许对点进行状压是一个思路。先考虑如何统计环的数量。假设点 $i$ 到点 $j$ 有 $5$ 条简单路径，点 $i$ 和点 $k$ 相连，点 $k$ 也和点 $j$ 相连。可以知道，必然存在 $5$ 个包含 $i, j, k$ 三个点的环。因此一个想法是，考虑统计环的个数转化为统计简单路径的条数。
设 $f_{i, j, s}$ 表示集合 $s$ 中从 $i$ 到 $j$ 的简单路径条数。值得注意的是，在无向图中，$i \rightarrow j \rightarrow k$、$j \rightarrow k \rightarrow i$、$k \rightarrow i \rightarrow j$ 三种递推关系本质上是在描述同一个环。观察并计算运算量，$19 ^ 2 \times 2 ^ {19} = 189267968$，无法使用数组存下所有的状态，因此考虑一个在动态规划中比较常见的技巧：按秩转移。
此处可以将 “秩” 理解为 “顺序”。为了使同一个集合内的点是按顺序转移的，考虑使用 $lowbit(s)$ 来记录答案。整个算法流程可以理解为对于每个状态，枚举其中的元素 $i$，同时枚举一个元素 $j$。若 $j$ 在 $s$ 里，按照上文分析的只有 $lowbit(s) = j$ 时要计入答案；如果 $j$ 不在 $s$ 里，就可以将方案数从 $s$ 转移到 $s \cup \{ j \}$ 这个集合。
于是最后时间复杂度为 $\mathcal O(n^2 \cdot 2^n)$，空间复杂度 $\mathcal O(n \cdot 2^n)$。其中由于并不会跑满，所以可以较为轻松地通过。
for (int s = 1, i = 1; i <= n; s <<= 1, i++) f[s][i] = 1;
for (int s = 1; s <= (1 << n); s++) {
for (int i = 1; i <= n; i++) {
if (!((1 << (i - 1)) & s) || !f[s][i]) continue;
for (int j = 1; j <= n; j++) {
if (lowbit(s) > (1 << (j - 1)) || !e[i][j]) continue;
if (lowbit(s) == (1 << (j - 1))) ans += f[s][i];
else if (!((1 << (j - 1)) & s)) f[s ^ (1 << (j - 1))][j] += f[s][i];
}
}
}
std::cout << ((ans - m) >> 1) << '\n';
例4：P3959 [NOIP2017 提高组] 宝藏
一个比较简单的思路是把树高，即道路的长度加到状态里。那么就可以有 $f_{s, h}$ 表示现在选的点集为 $s$，树高为 $h$ 的最小花费。不难得到转移方程：
\[f_{s, i} = \min_{t \in s} \\{ f_{t, i - 1} + cost_{t \rightarrow s}}\]$cost_{t \rightarrow s}$ 所表示的花费应当在可接受的复杂度以内预处理出来，而使用 $\text{Floyd}$ 算法求解最短路径时的时间复杂度时 $\mathcal O(n^3)$。因此最终的复杂度就是 $\Theta (3^n \cdot n^2)$。
for (int t = s; t; t = (t - 1) & s)
其中 $t$ 就会遍历 $s$ 的全部子集。考虑优化，不难发现同一树高的所有结点可以同时转移。不妨设 $f_{s, t}$ 表示已选点集为 $s$，下一层要加入的点集为 $t$ 时，新加入的点与原有点之间最小边权之和。转移如下：
\[f_{s, t} = \min \\{ f_{s, t - lowbit(j)} + cost_{k, s} \\}, k = \log_2(lowbit(j))\]其中 $cost_{k, s}$ 表示点 $k$ 到连通块 $s$ 的最短距离。至于为何使用 $lowbit(j)$ 来转移，原因是此时一个集合内的点依旧是无序的，所以可以进行 “按秩转移”。考虑基于对 $f$ 预处理的 $\text{DP}$。设 $g_{s, h}$ 表示已选点集为 $s$，当前树高为 $h$ 的最小花费。那么有转移：
\[g_{s, h} = \sum_{t \in s} g_{s - t, h - 1} + h \cdot f_{s - t, t}\]因此最后的时间复杂度就是 $\mathcal O(3^n \time n)$。而最终答案应当是对所有 $g_{s^n - 1, h}, h \in [1, n]$ 中取最小值。
for (int i = 0; i <= n; i++) f[0][1 << i] = 0;
for (int i = 1; i < (1 << n); i++) {
int c = ((1 << n) - 1) ^ i;
int next[(1 << n) + 10];
int last = 0;
for (int j = c; j; j = (j - 1) & c) next[j] = last, last = j;
for (int j = last; j; j = next[j]) {
int now = log[lowbit(j)] + 1;
int t = inf;
for (int k = 1; k <= n; k++) {
if (1 << (k - 1) & i) {
t = std::min(t, a[now][k]);
}
}
d[i][j] = d[i][j ^ lowbit(j)] + t;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < (1 << n); j++) {
for (int k = j; k; k = (k - 1) & j) {
f[i][j] = std::min(f[i][j], f[i - 1][j ^ k] + i * d[j ^ k][k]);
}
}
}
for (int i = 0; i <= n; i++) ans = std::min(ans, f[i][(1 << n) - 1]);
例5：P4484 [BJWC2018]最长上升子序列
对于一个排列，把数从小到大插入到一个空的数列里面，即增量转移。首先令 $\max(L_i)$ 表示前缀最大值，即
\[\max(L_i) = \max(f_1, f_2, \cdots, f_i)\]而对于 $\{ \max(L_i) \}$ 这个数列，有一个显然的性质：
\[\max(L_i) \le \max(L_{i + 1}) \le \max(L_i + 1)\]基于此可以发现 $\{ \max(L_i) \}$ 有差分性。不难发现，差分之后的序列必然只会由 $0 / 1$ 组成。不妨设该差分序列为 $\{ dif_n \}$。
在把每个数由小到大插入的过程中，对于序列 $\{ dif_n \}$ 会出现如下情况：某时刻，在第 $i$ 位和第 $i + 1$ 位之间插入了一个新的数。因为是单调插入的，所以该数一定是当前序列的最大值。那么不难发现该新插入数的 $\max(L)$ 一定等于 $\max(L_i) + 1$，$dif_{i + 1} = 1$；而在 $i$ 之后第一个比 $a_i$ 大大数，记其位置为 $p$，则 $dif_p$ 的值肯定也会为 $1$，因此应当把 $dif_p$ 置成 $0$。
不妨令 $g_{i, j}$ 表示在一个 $1 \sim i$ 的排列里，差分序列 $\{ dif_n \}$ 状态为 $j$ 的方案数，转移有：
\[ans = \frac{1}{n!} \sum_{i = 0}^{2^{n - 1} - 1} g_{n, i} \times popcount(i)\]也就是：
\[\sum 有 n 个数、状态为 i 的方案 \tims 方案中的 \text{LIS} 的长度\]由于状压了 $dif$ 数组，所以每个方案中 $\text{LIS}$ 的长度，就是该状态里 $1$ 的个数。而 $g$ 的转移较为清晰：
\[g_{i, j} = \sum g_{i - 1, k}\]