“状态压缩动态规划”中的状态,通常与集合相关联。集合本身具有确定性、互异性和无序性 3 个性质,这也就决定了集合只关心每个元素的存在状态,而这通常可以使用 0 或者 1 表示存在或者不存在。例如,有 8 个物品,对这 8 个物品的选取方案,必然是某个子集。令 1 表示选了,0 表示没选,那么像 10000001 就表示选了两端的两个物品,01010101 也是类似的道理。
由此可见,可以通过一串 0、1 码来清晰地表示一个集合的状态。同时,在确定了位数的前提下,一串 0、1 码与一个二进制数一一对应。这种表示状态的方式被称为状态压缩,简称状压。所谓“压缩”,即是用一个二进制数来保存一组状态,将一个集合的状态压缩进了一个二进制数中,而通常这个二进制数在十进制下的大小可以作为其编号。状态压缩本质上是进行了两步操作:
- 给这个集合的每个状态一个编号
- 通过该编号,轻易地访问该状态
例题:P1896 [SCOI2005] 互不侵犯
简单模拟后不难发现,答案可能会很大。而对于较复杂的计数,动态规划的思想往往是解决此类问题的有力武器。通过观察性质,不难发现按一定顺序,例如行号递增的方式摆放棋子时,当前棋子能不能放到某个位置上完全取决于上一行的棋子是怎么摆放的。因此,设计状态时可以将当前行、上一行的状态都记录下来,使用 0 或者 1 来表示某一行的状态,考虑用二进制数来表示。例如 \(101010_{(2)} = 34_{(10)}\),那么,对于这一行的状态,就可以用 34 这个十进制数值来记录。此时需要注意,一般情况下状压之后,状态中的每一位都是倒着存储的,因为这符合二进制的定义规则。例如一行的状态为 110101,那么二进制下应该是 101011。可以类比,从左至右列标逐渐增大,但是二进制位从左到右权值逐渐减小。
这种访问方式可以实现比数组寻址更快速、但同样准确的访问,如 *(1<<(k-1))&S
可以询问状态 S
的第 k
位上是 1 还是 0。而 (S>>k)<<k
则可以表示把状态 S
的二进制表示下最右边几位清零,而数组不能以 \(O(1)\) 的复杂度直接清零。
摆放国王需要满足两个约束条件:
- 行内约束:在同一行中,任意两个国王不能相邻。对于一个状态
S
,这意味着不能存在两个相邻的 1,用位运算可以表示为S & (S << 1) == 0
。 - 行间约束:第 \(i\) 行的国王不能攻击到第 \(i-1\) 行的国王,假设第 \(i\) 行的状态是 \(S\),第 \(i-1\) 行的状态是 \(P\),那么:
(S & P) == 0
(正上方不能有国王)(S & (P << 1)) == 0
(左上方不能有国王)(S & (P >> 1)) == 0
(右上方不能有国王)
基于以上分析,可以设计出 DP 方案。
需要记录三个关键信息:当前处理到哪一行、已经放了多少个国王、以及当前行的布局状态。因此,可以定义一个三维 DP 数组,令 \(f_{i,j,S}\) 表示在棋盘的前 \(i\) 行,总共放置了 \(j\) 个国王,并且第 \(i\) 行的布局状态为 \(S\) 的方案数。
从上一行 \(i-1\) 的状态 \(P\) 转移到当前行 \(i\) 的状态 \(S\)。
\(f_{i,j,S}\) 的值,等于所有可以转移到它的、上一行状态的方案数之和。具体来说,对于一个合法的当前行状态 \(S\),它包含 \(\text{count}(S)\) 个国王,这个状态可以由任何一个与它兼容的上一行状态 \(P\) 转移而来。从 \(P\) 转移时,上一行及之前已经放了 \(j-\text{count}(S)\) 个国王。
因此,状态转移方程为 \(f_{i,j,S} = \sum f_{i-1,j-\text{count}(S),P}\),其中求和的范围是所有与 \(S\) 兼容的上一行状态 \(P\)。
初始化\(f_{0,0,0}=1\),这可以理解为在第 0 行(一个虚拟的空行),放置 0 个国王,状态为 0(空),有 1 种方案,这是整个 DP 的起点。
当所有行都处理完毕后,需要的总方案数是所有在第 \(N\) 行、总国王数为 \(K\) 的方案之和。
这样时间复杂度为 \(O(NK 4^N)\)。
为了提高 DP 的效率,可以预处理一些信息:
- 合法单行状态:筛选出所有满足“行内约束”的状态 \(S\),并将它们存入一个数组。同时,可以预计算每个合法状态 \(S\) 中包含的国王数量(即二进制中 1 的个数)。
- 兼容状态对:对于每一个合法的单行状态 \(P\),可以预处理出所有能够作为其下一行的合法状态 \(S\)(即满足“行间约束”),并将这些兼容关系存储起来。
预处理合法单行状态后时间复杂度为 \(O(NKC^2)\),其中 \(C\) 是单行合法状态的数量。通过预处理兼容状态对,可以将复杂度优化为 \(O(NKT)\),其中 \(T\) 是所有兼容状态对的总数。对于 \(N=9\),\(C\) 在 100 左右,\(T\) 在 700 左右。
参考代码
#include <cstdio>typedef long long LL;
const int MAXN = 550; // 状态数的上限,2^9=512int c[MAXN]; // c[s]: 状态s中1的个数(即国王数量)
int s[MAXN]; // s[i]: 第i个合法的单行状态
int valid[MAXN][MAXN]; // valid[i][j]: 与状态s[i]兼容的第j个状态
int len[MAXN]; // len[i]: 与状态s[i]兼容的状态总数// dp[i][j][s]: 在第i行,放置了j个国王,且第i行状态为s时的方案数
// 使用滚动数组优化第一维
LL dp[2][100][MAXN];// 计算二进制数中1的个数 (population count)
int popcnt(int x) {int res = 0;while (x) {res++;x &= (x - 1); // 每次去掉最后一个1}return res;
}int main()
{int n, k;scanf("%d%d", &n, &k);// 1. 预处理:找出所有合法的单行状态int cnt = 0; // 合法状态的总数for (int i = 0; i < (1 << n); i++) {// 行内约束:国王不能左右相邻。 (i & (i >> 1)) == 0if (!(i & (i >> 1))) {s[cnt++] = i; // 存入合法状态数组c[i] = popcnt(i); // 预计算该状态的国王数}}// 2. 预处理:找出所有兼容的两行状态对for (int i = 0; i < cnt; i++) { // 枚举上一行的状态 s[i]for (int j = 0; j < cnt; j++) { // 枚举当前行的状态 s[j]// 行间约束:国王不能正上、左上、右上攻击// !(s[i] & s[j]): 正上方不能有国王// !(s[i] & (s[j] >> 1)): 左上方不能有国王// !(s[i] & (s[j] << 1)): 右上方不能有国王if (!(s[i] & s[j]) && !(s[i] & (s[j] << 1)) && !(s[i] & (s[j] >> 1))) {valid[i][len[i]++] = s[j]; // 记录兼容状态}}}// 3. 动态规划// 初始化 base case: 第0行,放0个国王,状态为0(空),方案数为1dp[0][0][0] = 1;for (int i = 1; i <= n; i++) { // 枚举当前行 iint cur = i % 2; // 当前行在滚动数组中的索引int pre_idx = 1 - cur; // 上一行在滚动数组中的索引// 清空当前行的dp值(如果滚动数组不清空,会沿用上上轮的结果)for (int j = 0; j <= k; j++) {for (int x = 0; x < cnt; x++) {dp[cur][j][s[x]] = 0;}}for (int j = 0; j <= k; j++) { // 枚举到当前行i为止,总共放置的国王数 jfor (int x = 0; x < cnt; x++) { // 枚举上一行(i-1)的合法状态 pre_state = s[x]int pre_state = s[x];for (int y = 0; y < len[x]; y++) { // 枚举与 pre_state 兼容的当前行(i)的状态 cur_stateint cur_state = valid[x][y];int kings_in_cur = c[cur_state]; // 当前行放置的国王数if (j >= kings_in_cur) { // 确保总国王数足够// 状态转移方程:// 当前方案数 += 上一行(状态为pre_state,国王数为j-kings_in_cur)的方案数dp[cur][j][cur_state] += dp[pre_idx][j - kings_in_cur][pre_state];}}}}}// 4. 统计最终答案// 最终答案是第 n 行,总共放了 k 个国王的所有状态的方案数之和LL ans = 0;for (int i = 0; i < cnt; i++) {ans += dp[n % 2][k][s[i]];}printf("%lld\n", ans);return 0;
}
习题:P2831 [NOIP 2016 提高组] 愤怒的小鸟
解题思路
由于小猪的数量 \(n\) 最多为 \(18\),暗示时间复杂度中可能有指数项,考虑状压 DP。
用一个整数的二进制位来表示小猪们的存活状态,一个 \(n\) 位的二进制数,第 \(i\) 位为 \(1\) 表示第 \(i\) 只小猪已经被消灭,为 \(0\) 则表示还存在。
设 \(dp_S\) 表示要达到状态 \(S\)(即消灭 \(S\) 这个二进制数所代表的小猪集合)所需的最少小鸟数量。最终目标是计算 \(dp_{2^n-1}\) 的,其中 \(2^n-1\) 是一个所有位都为 \(1\) 的 \(n\) 位二进制数,代表所有小猪都被消灭的状态。
为了加速动态规划的过程,可以预先计算出任意两只小猪(或一只小猪)能确定的抛物线可以一次性消灭哪些小猪。
一条经过原点的抛物线 \(y=ax^2+bx\) 可以由两个不同的小猪坐标 \((x_i,y_i)\) 和 \((x_j,y_j)\) 唯一确定(前提是 \(x_i\) 不等于 \(x_j\)),通过解二元一次方程组可以求出 \(a\) 和 \(b\)。如果只选一只小猪 \((x_i,y_i)\),它自己就能构成一条抛物线(可以有无数条,但这里只关心它能打掉自己)。
用一个二维数组 \(c_{i,j}\) 来存储这个预处理结果,\(c_{i,j}\) 是一个整数(同样用作位掩码),表示由第 \(i\) 只和第 \(j\) 只小猪确定的抛物线所能消灭的所有小猪的集合。
初始化 \(dp_0 = 0\)(消灭 \(0\) 只小猪需要 \(0\) 只小鸟),其他 \(dp_S\) 初始化为一个较大的值,表示初始时不可达。
从小到大遍历所有状态 \(S\),对于每个状态 \(S\),找到第一个还未被消灭的小猪 \(p\),发射一只小鸟来消灭 \(p\)。这只小鸟可以只打 \(p\),也可以再打另一只小猪 \(j\),那么这次打击会消灭 \(c_{p,j}\) 所代表的小猪集合。新的状态就是当前状态和这次打击所消灭的小猪集合的并集,用当前的 \(dp\) 值加 \(1\) 尝试更新新状态的 \(dp\) 值。
参考代码
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 18;
const double EPS = 1e-6;
double x[N], y[N];
int c[N][N]; // c[i][j] 存储由猪i和猪j决定的抛物线能覆盖的小猪集合(位掩码)
int dp[1 << N]; // dp[S] 存储达到状态S所需的最少小鸟数
bool match(double a, double b, int i) { // 检查点(x[i],y[i])是否在由a和b定义的抛物线上double res = a * x[i] * x[i] + b * x[i];return fabs(res - y[i]) < EPS; // 考虑浮点误差
}
int main()
{int t;scanf("%d", &t); // 读取测试用例数量while (t--) {int n, m; scanf("%d%d", &n, &m); // 正解用不到mfor (int i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);// 预处理阶段:计算 c 数组,存储所有可能的单次打击结果for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {c[i][j] = 1 << i; // 如果只选一只猪,抛物线只经过它自己continue;} else if (x[i] == x[j]) continue; // 如果两只猪的x坐标相同,无法形成抛物线c[i][j] = 0;// 解方程组 y = ax^2 + bx// y_i = a*x_i^2 + b*x_i// y_j = a*x_j^2 + b*x_j// 消去 b,解出 a 和 bdouble denom = x[i] * x[j] * (x[i] - x[j]);double a = (x[j] * y[i] - x[i] * y[j]) / denom;double b = (y[j] * x[i] * x[i] - y[i] * x[j] * x[j]) / denom;if (a > -EPS) continue; // a 必须是负数// 找到这条抛物线能打掉的所有猪for (int k = 0; k < n; k++) {if (match(a, b, k)) c[i][j] |= (1 << k); // 使用位运算来构建集合} }}// 动态规划阶段for (int i = 0; i < (1 << n); i++) dp[i] = n; dp[0] = 0;for (int i = 0; i < (1 << n) - 1; i++) { // 遍历所有可能的状态if (dp[i] == n) continue;// 找到第一个还没被打掉的猪int p = 0;for (int j = 1; j < n; j++) if (!((i >> j) & 1)) { // 检查第j位是否为0p = j; break;}// 尝试用一只小鸟打掉这只猪 p// 这只小鸟可以顺便打掉另一只猪 jfor (int j = 0; j < n; j++) {if (p != j && x[p] == x[j]) continue;int nxt = i | c[p][j]; // 新状态是当前状态 i 和 c[p][j] 的并集dp[nxt] = min(dp[nxt], dp[i] + 1); // 状态转移:用更少的鸟数更新到达nxt状态的记录}}printf("%d\n", dp[(1 << n) - 1]);}return 0;
}