数据结构与算法学习笔记----动态规划·状态压缩DP
@@ author: 明月清了个风
@@ first publish time: 2025.5.24ps⭐️这一篇是关于状态压缩DP的，基础课中已经讲过了基本的题目，链接在这，可以先去复习一下。主要分为两种：棋盘式(基于连通性)和集合式，一共四道题目，还是比较难得。
Acwing 1064. 小国王
在 n × n n \times n n×n的棋盘上放 k k k个国王，国王可攻击相邻的 8 8 8个格子，求使它们无法互相攻击的方案总数。
输入格式
共一行，包含两个整数 n n n和 k k k。
输出格式
共一行，表示方案总数，若不能够放置则输出 0 0 0。
数据范围
1 ≤ n ≤ 50 1 \le n \le 50 1≤n≤50,
0 ≤ k ≤ n 2 0 \le k \le n^2 0≤k≤n2
思路
这一题和基础课中讲过的蒙德里安的幻想的区别是格子的连通性不同，本题中国王周围的 8 8 8个格子都不能再放。
如果按行来摆国王的话，可以发现，每一行的摆放情况只与上一行的情况有关，上上行无论怎么摆都不会影响到当前行的情况，因此可以对当前行的状态进行划分。
对于状态表示，使用 f [ i ] [ j ] [ s ] f[i][j][s] f[i][j][s]表示已经放好了前 i i i行，当前已经放了 j j j个棋子，且第 i i i行的状态为 s s s的摆法集合。第 i i i行的状态 s s s用一个 n n n位的二进制数表示，当对应位为 1 1 1时表示摆放了国王，为 0 0 0表示没有摆放。要求的集合是摆法的数量。
对于集合划分，需要根据倒数第二步进行划分，当前状态 s s s对比，判断是否合法。上一层的状态，也就是 i − 1 i - 1 i−1行的状态最多有 2 n 2^n 2n种方案，需要有一些限制条件进行筛选：
- 第 i − 1 i - 1 i−1行内部不能有相邻的两格同时摆放；
- 第 i − 1 i - 1 i−1行与第 i i i行之间也不能相互攻击；
用代码表示条件，假设第 i − 1 i - 1 i−1行的状态是 a a a，第 i i i行的条件是 b b b，那么一定有·a & b == 0，这样表示没有上下同一个位置同时摆放国王。；第二个条件a | b的结果不能有两个相邻的1。满足这两个条件即可。
那么当上一行的方案合法时，该方案数量首先要将最后一行去掉，也就是第 i i i行方案为 a a a，假设 a a a中有 c o u n t ( a ) count(a) count(a)个国王，那么就是 f [ i − 1 ] [ j − c o u n t ( a ) ] [ b ] f[i - 1][j - count(a)][b] f[i−1][j−count(a)][b]。
代码其实和蒙德里安的很相似。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N, K = 110;
int n, m;
LL f[N][K][M];
vector<int> state[M];
bool st[M];
int cnt[M];
bool check(int x)
{
for(int i = 0; i < n; i ++)
if(x >> i & 1 && x >> i + 1 & 1)
return false;
return true;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < 1 << n; i ++)
{
st[i] = check(i);
}
for(int i = 0; i < 1 << n; i ++)
{
int sum = 0;
for(int j = 0; j < n; j ++)
if(i >> j & 1) sum ++;
cnt[i] = sum;
}
for(int i = 0; i < 1 << n; i ++)
{
if(st[i])
for(int j = 0; j < 1 << n; j ++)
if((i & j) == 0 && st[i | j]) state[i].push_back(j);
}
f[0][0][0] = 1;
for(int i = 1; i <= n + 1; i ++)
for(int j = 0; j <= m; j ++)
for(int k = 0; k < 1 << n; k ++)
{
if(st[k])
{
for(int z : state[k])
{
if(j >= cnt[z]) f[i][j][k] += f[i - 1][j - cnt[z]][z];
}
}
}
cout << f[n+1][m][0] << endl;
return 0;
}
Acwing 327. 玉米田
农夫约翰的土地由 M × N M \times N M×N个小方格组成，现在他要在土地里终止玉米。
非常遗憾，部分土地是不育的，无法种植。
而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小，请你求出共有多少种种植方法。
土地上什么都不种也算一种方法。
输入格式
第一行包含两个整数 M M M和 N N N。
第 2 ⋯ M + 1 2 \cdots M+1 2⋯M+1行：每行包含 N N N个整数 0 0 0或 1 1 1，用来描述整个土地的状况， 1 1 1表示该块土地肥沃， 0 0 0表示该块土地不育。
输出格式
输出总种植方法对 10 8 10^8 108取模后的值。
数据范围
1 ≤ M ， N ≤ 12 1 \le M， N \le 12 1≤M，N≤12,
思路
这一题其实和上一题基本一致，只是这一题中只有周围四个格子不能摆放+坏掉的土地不能摆放。
对于状态表示，使用 f [ i ] [ s ] f[i][s] f[i][s]表示摆放了前 i i i行，且第 i i i行摆放情况为 s s s的摆法集合，属性是方案数。
对于状态划分，同样根据上一行的状态进行划分，假设上一行状态为 b b b，当前行状态为 a a a，要满足的第一个条件为一行中不能有连续的 1 1 1；第二个条件是两行不能在同一列中有相同的 1 1 1，也就是(a & b) == 0；
注意还要判别当前状态是否与地图有冲突，因为有的地是不能种的。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 14, M = 1 << 12, mod = 1e8;
int n ,m;
int f[N][M];
int g[N][M];
vector<int> state[M];
bool st[M];
bool check(int x)
{
for(int i = 0; i < m; i ++)
{
if(x >> i & 1 && x >> i + 1 & 1) return false;
}
return true;
}
bool valid(int x, int s)
{
for(int i = 0; i < m; i ++)
{
if(s >> i & 1 && !g[x][i]) return false;
}
return true;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 0; j < m; j ++)
cin >> g[i][j];
for(int i = 0; i < 1 << m; i ++) st[i] = check(i);
for(int i = 0; i < 1 << m; i ++)
{
if(st[i])
{
for(int j = 0; j < 1 << m; j ++)
if((i & j) == 0 && st[j]) state[i].push_back(j);
}
}
f[0][0] = 1;
for(int i = 1; i <= n + 1; i ++)
for(int j = 0; j < 1 << m; j ++)
{
if(valid(i, j))
{
for(int k : state[j])
if(valid(i - 1, k)) f[i][j] += f[i - 1][k];
}
}
cout << f[n + 1][0] % mod << endl;
return 0;
}
Acwing 292. 炮兵阵地
司令部的将军们打算在 N × M N \times M N×M的网格地图上部署他们的炮兵不对。
一个 N × M N \times M N×M的地图由 N N N行 M M M列组成，地图上的每一格可能是山地（用H表示），也可能是平原（用P表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个整数 N N N和 M M M。
接下来 N N N行，每一行含有连续的 M M M个字符(p或H)，中间没有空格。按顺序表示地图中每一行的数据。
输出格式
进一行，包含一个整数 K K K，表示最多能摆放的炮兵部队的数量。
数据范围
N ≤ 100 , M ≤ 10 N \le 100, M \le 10 N≤100,M≤10
思路
相较于上面两道题目，这道题目的占位变得更大，不仅仅与上一行的摆放情况有关，一个炮兵会影响接下来的两行。
因此需要在状态表示中添加一维用来表示上上行的状态。使用 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]，所有已经摆放了前 i i i行，且 i i i行摆放状态为 j j j， i − 1 i - 1 i−1行摆放情况为 k k k的摆法集合，属性是最大值。
同样地，根据最后一步的情况进行划分，由于此处第 i i i行与第 i − 1 i - 1 i−1行的状态的都已经确定，因此最后一步就是 i − 2 i - 2 i−2行的状态。
假设第 i − 1 i - 1 i−1行状态是 a a a，第 i i i行状态是 b b b，第 i − 2 i - 2 i−2行状态是 c c c，那么需要满足的条件为((a & b) | (a & c) | (b & c)) == 0；其次，需要满足地图的条件，不能放在山地上，因此(g[i - 1] & a) | (g[i] & b) == 0。
时间复杂度为 n ∗ 2 3 m n * 2^{3m} n∗23m会超时，但是其实在状态的转移中会有非常多的无效状态，因此并不会超时。
需要注意的是这里的状态需要用滚动数组来做，不然会超内存。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 12, M = 1 << 10;
int n, m;
int g[110];
vector<int> state;
int f[2][M][M];
int cnt[M];
bool st[M];
bool check(int x)
{
for(int i = 0; i < m; i ++)
if(x >> i & 1 && ((x >> i + 1 & 1) || (x >> i + 2 & 1)))
return false;
return true;
}
int count(int state)
{
int res = 0;
for(int i = 0; i < m; i ++) res += state >> i & 1;
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 0; j < m; j ++)
{
char c;
cin >> c;
if(c == 'H') g[i] += 1 << j;
}
for(int i = 0;i < 1 << m; i ++)
if(check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
for(int i = 1; i <= n + 2; i ++)
for(int j = 0; j < state.size(); j ++)
for(int k = 0; k < state.size(); k ++)
for(int u = 0; u < state.size(); u ++)
{
int a = state[j], b = state[k], c = state[u];
if((a & b) | (b & c) | (a & c)) continue;
if(g[i - 1] & a | g[i] & b) continue;
// 滚动数组，所有的一维下标&1可以将下标限制在0或1,一定是奇偶交替滚动的
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
}
cout << f[n + 2 & 1][0][0] << endl;
return 0;
}
Acwing 524. 愤怒的小鸟
Kiana 最近沉迷于一款神奇的游戏无法自拔。
简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于 ( 0 , 0 ) (0,0) (0,0)处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟， 小鸟们的飞行轨迹均为形如 y = a x 2 + b x y = ax^2 + bx y=ax2+bx的曲线，其中 a , b a,b a,b都是 是 Kiana 指定的参数，且必须满足 a < 0 a < 0 a<0。
当小鸟落回地面（即 x x x轴）时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有 n n n只绿色的小猪，其中第 i i i只小猪所在的坐标为 ( x i , y i ) (x_i, y_i) (xi,yi)。
如果某只小鸟的飞行轨迹经过了 ( x i , y i ) (x_i,y_i) (xi,yi)，那么第 i i i只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；
如果某只小鸟的飞行轨迹没有经过 ( x i , y i ) (x_i,y_i) (xi,yi)，那么这只小鸟飞行的全过程不会对第 i i i只小猪产生任何影响；
例如，若两只小猪分别位于 ( 1 , 3 ) (1,3) (1,3)和 ( 3 , 3 ) (3,3) (3,3)，Kiana 可以选择发射一只飞行轨迹为 y = − x 2 + 4 x y = -x^2 + 4x y=−x2+4x的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个这个游戏。
这些指令将在输入格式中详述。
假设这款游戏一共有 T T T个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。
由于她不会算，所以希望由你告诉她。
输入格式
第一行包含一个整数 T T T，表示游戏的关卡总数。
下面依次输入这 T T T个关卡的信息。
每个关卡第一行包含两个非负整数$ n,m$，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。
接下来的$ n 行中，第 行中，第 行中，第i$行包含两个正实数 ( x i , y i ) (xi,yi) (xi,yi)，表示第 ii 只小猪坐标为 ( x i , y i ) (xi,yi) (xi,yi)，数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果$ m=0$，表示 Kiana 输入了一个没有任何作用的指令。
如果$ m=1 ，则这个关卡将会满足：至多用 ，则这个关卡将会满足：至多用 ，则这个关卡将会满足：至多用 ⌈n/3+1⌉$只小鸟即可消灭所有小猪。
如果$ m=2 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 ⌊n/3⌋$只小猪。
保证$ 1≤n≤18，0≤m≤2，0<xi,yi<10$，输入中的实数均保留到小数点后两位。
上文中，符号$ ⌈c⌉ 和 和 和 ⌊c⌋ 分别表示对 分别表示对 分别表示对 c 向上取整和向下取整，例如： 向上取整和向下取整，例如 ： 向上取整和向下取整，例如：⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3$。
输出格式
对每个关卡依次输出一行答案。
输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。
数据范围
本题除 NOIP 原数据外，还包含加强数据。
思路
首先可以确定这道题和上面的题目并不是一个类型的棋盘类问题，为一个重复覆盖问题。根据题意，抛物线肯定经过原点，因此只需额外的两个点就可以确定一个抛物线了（当然，两个点的 x x x坐标不能相同），这道题中的 m m m其实没有啥用。
由于题目会给出 n n n个点，因此一共可以得到最多 n 2 n^2 n2条抛物线，一个思路就是先把这些抛物线预处理出来，判断能够经过的点，这个问题就变成了给定 x x x条抛物线，最少需要几条抛物线能够覆盖所有的点。之前在 d f s dfs dfs中学习过的八皇后问题为精确覆盖问题，而这里的点可以重复覆盖，对于这种问题的最优解法是 D a n c i n g l i n k s Dancing links Dancinglinks，但是比较难写。
这里的解法是通过集合类型的状态压缩DP优化DFS的过程。
考虑DFS的过程
int dfs(int state) // state存储哪些列已经被覆盖了
{
if(state 已经包含所有列) return 0;
int res = inf;
任选没有被覆盖的一列x
枚举所有能覆盖x的抛物线
更新state --> new_state
res = min(dfs(new_state) + 1);
return res;
}
然后考虑如何优化，首先对于任意一个state，一定会对应一个最小值res，因此可以将这个值记录到DP数组 f [ s t a t e ] f[state] f[state]中。
接下来是对于在上述过程中任选的没有被覆盖的一列 x x x，枚举所有能够覆盖他的抛物线path[x][j]，更新状态为new_state = state | path[x][j],上述 d f s dfs dfs过程变为
void dfs(int state, int cnt) // state存储哪些列已经被覆盖了
{
if(state 已经包含所有列) ans = min(ans, cnt), return ;
int res = inf;
任选没有被覆盖的一列x
枚举所有能覆盖x的抛物线
更新state --> new_state
(dfs(new_state), cnt + 1);
}
最后就是如何处理出抛物线，这就是数学问题了，就是两个点确定一条抛物线，具体的看代码吧，注释比较多
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 18, M = 1 << 18;
const double eps = 1e-6;
int n, m;
PDD q[N]; // 存点
int path[N][N]; // path[i][j]表示由第i个点与第j个点确定的抛物线
int f[M]; // DP数组
bool cmp(double x, double y) // 判断两个数关系，浮点数需要有精度。
{
if(fabs(x - y) < eps) return 0;
if(x < y) return -1;
return 1;
}
int main()
{
int T;
cin >> T;
while(T --)
{
cin >> n >> m;
for(int i = 0; i < n; i ++) cin >> q[i].x >> q[i].y;
memset(path, 0, sizeof path);
for(int i = 0; i < n; i ++)
{
path[i][i] = 1 << i; // 同样的点用1标记
for(int j = 0; j < n; j ++)
{
double x1 = q[i].x, y1 = q[i].y; // 遍历所有点，每两个点确定一条抛物线
double x2 = q[j].x, y2 = q[j].y;
if(!cmp(x1, x2)) continue;
double a = (y1 / x1 - y2 / x2) / (x1 - x2); // 计算系数
double b = y1 / x1 - a * x1;
if(a >= 0) continue;
int state = 0; // 记录状态
for(int k = 0; k < n; k ++) // 遍历所有点，看是否被上面计算出的抛物线覆盖了
{
double x = q[k].x, y = q[k].y;
if(!cmp(a * x * x + b * x, y)) state += 1 << k; // 一个点被覆盖了就标记对应的位置
}
path[i][j] = state; // 表示由(i,j)两点确定的抛物线经过的所有点
}
}
memset(f, 0x3f, sizeof f);
f[0] = 0; // 没有点被覆盖线的数量当然是0
for(int i = 0; i + 1 < 1 << n; i ++) // 当已经包含所有列的时候不需要更新了，因此是i + 1 < 1 << n，跳过最后一个状态
{
int x = 0; // 记录要下一个要覆盖的点
for(int j = 0; j < n; j ++) // 遍历找一个没有每覆盖的点
if(!(i >> j & 1)) // 当前状态没有覆盖第j个点，那就选他
{
x = j;
break;
}
for(int j = 0; j < n; j ++) // 更新状态，遍历其他所有点，就能确定(x,j)的抛物线经历了哪些点，通过或运算更新状态，同时更新数量
f[i | path[x][j]] = min(f[i] + 1, f[i | path[x][j]]);
}
cout << f[(1 << n) - 1] << endl;
}
return 0;
}