Flaw_Owl 的状压 DP 题单

# 状态压缩 DP ## 概念 状态压缩是 DP 的一个技巧，主要用来处理**集合问题**。 当 DP 的状态是一个集合的时候，我们就把集合的组合或排列用一个**二进制数**表示，这个二进制数的 0/1 用来表示集合的一个子集。这时我们就可以方便地用二进制的位运算来处理复杂的集合变动关系。 ## 引子: Hamilton 问题 下面用一个例子来介绍状态压缩 DP [经典状压 DP 问题：P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433 "比较经典，和经典 Hamilton 的差别在于没有指定终点") **题目简介**：房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。 这种在**有权无向图**中，求从起点到某个终点，**必须经过所有点，且每个点只经过一次**的问题，被称为 **Hamilton (旅行商)** 问题。 Hamilton 问题是 NP问题，不存在多项式复杂度的解法。 ### 暴力求解？ 如果尝试暴力，我们就需要列出所有 $n$ 个点的全排列，共有 $n!$ 个，一个全排列就是一种可能的路径。如果我们预先处理好每两个点的距离，那么计算每一种可能路径的总长度就是 $n$ 次。最后，我们还需要找出最短的路径，可以解算出时间总复杂度是 $O(n \times n!)$。这是不可接受的。 ### DP 思路 我们重新考虑。作为聪明的鼠鼠，我们在进行移动之前可以先观察周围，利用一点贪心的思路，先计算出在观察范围内最好的路径；然后我们把眼光逐步放大，每一次就多包括一点奶酪……最后，我们就能找出在整张地图下最好的路径。 那么这就是 DP 的求解思路。对于 DP 题，我们可以从以下几个角度思考： 1. 如何定义 DP 状态 2. DP 的起始、终止状态 3. 状态转移方程 我们首先**定义 DP 状态**。令 `dp[S][j]` 表示在某个集合 $S$（即鼠鼠当前看到的奶酪范围）下，从起点经过 $S$ 内所有的点，最终到达终点 $j$ 的最短路径。DP 的终止状态，当然就是 `dp[N][n]` 其中 $N$ 表示图上所有点的集合状态，$n$ 表示已经走到了第 $n$ 块奶酪。 DP接下来的问题来到如何转移状态。DP 的思路就是 **从小问题推到大问题**。小问题就是它的前一个状态，即从 $S-j$，表示不包含 $j$ 点的集合状态，推导到 $S$。 假设 $k$ 是 $S-j$ 中的一个点，我们可以把它分为 $1 \sim k$ 和 $k \sim j$ 两个部分。以 $k$ 为变量枚举 $S-j$ 中所有点，找出最短的路径。 什么叫以 $k$ 作为变量？具象来说（从鼠鼠的视角来看），就是找出一个点 $k$，从当前状态到那的距离，再加上那个点到目标点 $j$ 的距离，最小的路径就是最好的路径。 所以我们写出状态转移方程： $$f(S,j) = \min \{ f(S-j,k) + dis(k,j) \}$$ 其中 $dis(k,j)$ 表示预先处理好的从 $k$ 到 $j$ 的距离。 ### 用二进制来表示集合状态：状态压缩 以上其实都只是 DP 的部分。可以发现，我们的求解难点是如何对集合 $S$ 进行操作。 我们用一个二进制串来表示 $S$ 的状态：对于每一个点，$1$ 表示 $S$ 包含这个点，$0$ 表示不包含。在本题中一共有 $n$ 块奶酪，再加上起点，一共 $n+1$ 个点，就用一个长度为 $n+1$ 的字符串进行记录。 所以，起始状态就是 $S=1$，表示除了最后一位（起点）为 $1$ 之外，其他的点都还没被包含到 $S$ 中。终止状态就是 $S =(1<<n) - 1$，每一位都是 $1$，表示每一个点都被包含到了集合中。 那么我们如何枚举 $S-j$ 中所有的点呢？这时候就需要用到位运算。 `if ((S >> j) & 1)`，在位运算中实际表示“将 $S$ 右移 $j$ 位，再和 $1$ 进行与运算”，目的是将目标位 $j$ 移动到最右边，和 $1$ 进行与运算后，如果为 $1$，则表示这一位存在，反之则不存在。在代码中的意义是判断状态 $S$ 下是否存在 $j$ 点。 `if (S ^ (1 << j) >> k & 1)`，前半部分 `S ^ (1 << j)` 指的是将 $S$ 去掉点 $j$。后半部分是用 $k$ 来遍历每一个点。 ```cpp /** * @file Luogu_P_1433 吃奶酪 * @ * @brief * @version 0.1 * @date 2024-04-08 */ #include <iostream> #include <cctype> #include <cmath> #include <string.h> using namespace std; const int INF = 0x3f3f3f3f; int n; double ans = INF; double dp[(1 << 16) + 5][20]; // dp[S][j] 表示状态 S 且终点为 j 的情况下最短路径的距离。最多 15 块奶酪，故S = 1 << 15 + 5 double dis[20][20]; // dis[i][j] 表示第 i 块奶酪到第 j 块奶酪之间的距离 struct node { double x, y; } point[20]; // 记录点 // 计算距离 double calculate(node a, node b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } // 初始化 void init() { memset(dp, 127, sizeof(dp)); // 初始化最大值，这很重要 scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lf%lf", &point[i].x, &point[i].y); point[0].x = 0; point[0].y = 0; // 预处理：每两个点之间的距离 for (int i = 0; i <= n; i++) for (int j = i + 1; j <= n; j++) { dis[i][j] = calculate(point[i], point[j]); dis[j][i] = dis[i][j]; } } int main() { init(); dp[1][0] = 0; // 起始情况：只有出发点存在，距离为 0 for (int S = 1; S < (1 << (n + 1)); S++) for (int j = 0; j <= n; j++) if ((S >> j) & 1) for (int k = 0; k <= n; k++) if ((S ^ (1 << j)) >> k & 1) { dp[S][j] = min(dp[S][j], dp[S ^ (1 << j)][k] + dis[k][j]); } for (int j = 0; j <= n; j++) ans = min(ans, dp[(1 << (n + 1)) - 1][j]); printf("%.2lf\n", ans); return 0; } ``` ## 基本的集合 - 位运算操作手段 注：以下的第 $i$ 位指的是二进制串的最低位开始，且最低位为第 $0$ 位。 |用途|操作| |:--:|:--:| |判断 $S$ 的第 $i$ 位是否为 $1$|`1 << i & S`| |把 $S$ 的第 $i$ 位改成 $1$|`S \| (1 << i)`| |把 $S$ 的第 $i$ 位改成 $0$|`S & (~(1 << i))`| |去掉 $S$ 的最后一个 $1$ |`S & (S-1)`| ## 应用：士兵问题 士兵问题指的是在一个规定大小的地图内放置士兵，但士兵之间存在相互攻击，因此放置受限的问题。 地图本身可能存在能否放置的问题，只需用 1/0 表示地块的可放置性，在计算的时候直接加上地块的值即可。 士兵之间的相互约束有很多种，但通常都使用 `if(i & (i << x) == 0 && (i & (i >> x)))` 来表示士兵无法放置在相距距离为 $x$ 的地块上的情况。 最终的询问可能有：最多放置士兵数量、给定数量士兵放置方案数目等等。 利用 DP 的思路，从第 $1$ 行开始，一行一行地放士兵，每行都判断合法性，直到最后一行。 ### 最多放置问题 [最经典的士兵问题：P2704 [NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/P2704) 这题的 DP 设计为 `dp[i][j][k]`，表示第 $i$ 行状态为 $j$，第 $i-1$ 行状态为 $k$ 的情况下，放置的士兵总数。 状态转移方程为： $$f(i,j,k) = \max \{ f(i-1,k,p) + cnt(i,sta(j)) \}$$ ```cpp dp[i][j][k] = max(dp[i-1][k][p] + count_line(i,sta[j])) ``` 其中，`count_line` 函数计算了第 $i$ 行在合法 $j$ 状态下的士兵数量；`p` 表示 $i-2$ 行的合法情况。 值得注意的是，如果直接将数组开到最大状态会严重 MLE。可以利用滚动数组优化，但最好的方式是**预处理出每一行的合法情况数目**，直接将数组开到这个数目即可。 ```cpp #include <iostream> #include <cctype> #include <string.h> using namespace std; const int maxN = 65; int read() { int x = 0, f = 1; char ch = 0; while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int n, m; int mp[105][15]; // 地图 int dp[105][maxN][maxN]; // dp[i][j][k] 表示第 i 行状态为 j，第 i-1 行状态为 k 的情况下最多的数量 int sta[maxN]; // 预计算出一行的合法情况。 // 预计算出一行的合法情况 int init_line(int n) { int res = 0; for (int i = 0; i < n; i++) if ((i & (i << 1)) == 0 && (i & (i >> 1)) == 0 && (i & (i << 2)) == 0 && (i & (i >> 2)) == 0) sta[res++] = i; return res; } // 计算第 i 行的数量 int count_line(int i, int x) { int sum = 0; for (int j = m - 1; j >= 0; j--) { if (x & 1) sum += mp[i][j]; x >>= 1; } return sum; } // 主函数 int main() { n = read(); m = read(); int M = init_line(1 << m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { char ch; cin >> ch; if (ch == 'P') mp[i][j] = 1; else mp[i][j] = 0; } int ans = -1; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) for (int j = 0; j < M; j++) for (int k = 0; k < M; k++) { if (i == 0) { dp[i][j][k] = count_line(i, sta[j]); ans = max(ans, dp[i][j][k]); continue; } if (sta[j] & sta[k]) continue; int tmp = 0; for (int p = 0; p < M; p++) { if (sta[k] & sta[p]) continue; if (sta[j] & sta[p]) continue; tmp = max(tmp, dp[i - 1][k][p]); } dp[i][j][k] = tmp + count_line(i, sta[j]); ans = max(ans, dp[i][j][k]); } printf("%d\n", ans); return 0; } ``` ### 方案数目问题 [求方案数目：P1896 [SCOI2005] 互不侵犯]("这道题最烦的地方其实是要开 long long") 这题的 DP 设计为 `dp[i][j][k]`，表示第 $i$ 行状态为 $j$，且已经用了 $k$ 个国王的情况下的方案总数。 与上题不同的是，我们每次不再选择“放置最多的状态”，而是“每一种状态”，所以在处理 `init()` 函数的时候要额外存储每一种状态的信息。 状态转移方程就是继承上一行的方案数。值得注意状态转移方程中： ```cpp for (int p = 0; p <= K; p++) if (p >= cnt[sta[j]]) dp[i][j][p] += dp[i - 1][k][p - cnt[sta[j]]]; ``` 这里我们枚举使用的国王数 $p$ 来进行转移，而不是对每个状态进行存储后再计算，算是一个~~反正我想不出来~~的技巧。 ```cpp #include <iostream> #include <cctype> #include <string.h> #define ll long long using namespace std; int read() { int x = 0, f = 1; char ch = 0; while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const int maxN = (1 << 9) + 5; const int maxM = 100; int n, K; ll dp[15][maxN][maxN]; // dp[i][j][p] 表示第 i 行放置状况为 j，且目前所用的国王数量为 p 的情况下的方案数 ll sta[maxN]; ll cnt[maxN]; int init_line(int n) { int M = 0; for (int i = 0; i < (1 << n); i++) { int tot = 0, s = i; while (s) { if (s & 1) tot++; s >>= 1; } cnt[i] = tot; if ((i & (i << 1)) == 0 && (i & (i >> 1)) == 0) sta[M++] = i; } return M; } // 计算当前行用的国王数量 int count_line(int i, int x) { int sum = 0; for (int j = n - 1; j >= 0; j--) { if (x & 1) sum++; x >>= 1; } return sum; } int main() { n = read(); K = read(); int M = init_line(n); memset(dp, 0, sizeof(dp)); for (int j = 0; j < M; j++) dp[0][j][cnt[sta[j]]] = 1; for (int i = 1; i < n; i++) // 枚举到第 i 行 for (int j = 0; j < M; j++) // 第 i 行的状态 j for (int k = 0; k < M; k++) // 第 i-1 行的状态 k { if ((sta[j] & sta[k]) || (sta[j] & (sta[k] >> 1)) || (sta[j] & (sta[k] << 1))) continue; for (int p = 0; p <= K; p++) if (p >= cnt[sta[j]]) dp[i][j][p] += dp[i - 1][k][p - cnt[sta[j]]]; } long long ans = 0; for (int i = 0; i < M; i++) ans += dp[n - 1][i][K]; printf("%lld\n", ans); } ```