状态压缩DP

种类

• 棋盘式（基于连通性）
• 集合

原理

使用二进制的方法表示状态。

时间复杂度计算

状态数量*状态计算的计算量

例题

AcWing 1064. 小国王

在 $n\times n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。

输入格式
共一行，包含两个整数 $n$ 和 $k$。

输出格式
共一行，表示方案总数，若不能够放置则输出 $0$。

数据范围
$1\le n\le 10,$
$0\le k\le n^2$

输入样例：

3 2

输出样例：

16

状态标识：$f[i][j][s]$ 表示所有只摆在前 $i$ 行，已经摆了 $j$ 个国王，并且第 $i$ 行摆放的状态是 $s$ 的所有选法的数量。
注意这里国王的数量是被限制的，所以要三维数组来表示状态。

对于S：我们让每个填入的格子为 $1$，没有填入的为 $0$。

假如填入了中间一行的两边的格子，那就标记成如上图所示，这个时候状态就为$(101{)}_2$，那么S就为二进制数对应的十进制数5。

对于每一行：

• 第 $i$ 行内部不能有两个 $1$ 相邻
• 第 $i-1$ 行和第 $i$ 行不能又相互攻击到的放法

如何判断相邻两行是合法的？
如果 $S_1$ 表示 $i-1$ 层，$S_2$ 表示第 $i$ 层的状态

• 满足 a & b == 0，即上下没有相邻的 $1$
• 满足 a | b不能有两个相邻的 $1$

状态计算：
在判断条件之后 如何算出每一次要加上的国王的数量

有两个状态。
一个是排完了前i排，第 $i$ 排状态是 $S1$ ，$i-1$ 排是 $S2$，摆了 $j$ 个国王。
一个是摆完前 $i-1$ 排，并且前 $i-1$ 排状态是 $S2$，摆了 $j$ 减去状态 $S1$ 里的 $1$ 的个数（即第 $i$ 排国王的数量）个国王。

所以 $f[i][j][s1]$ 就可以由 $f[i-1][j-count(s1)][s2]$ 转化而来。

代码：

#include<iostream>
#include<vector>
using namespace std;
const int N = 12, M = 1 << 10, K = 110;
#define ll long long

int n, m;
vector<int>st;		//存所有合法的状态
int cnt[M];			//cnt[i]存数字i二进制状态下1的个数
vector<int>head[M];	//存哪些状态可以转移到哪些状态
ll f[N][K][M];

bool check(int st) {	//验证是否是没有相邻的1
   for (int i = 0; i < n; i++) {
   	if ((st >> i & 1) && (st >> i + 1 & 1))return false;
   }
   return true;
}

int count(int st) {	//求出二进制中1的个数
   int res = 0;
   for (int i = 0; i < n; i++)res += st >> i & 1;
   return res;
}

int main() {
   cin >> n >> m;

   //枚举所有合法的状态并记录
   for (int i = 0; i < 1 << n; i++) {
   	if (check(i)) {
   		st.push_back(i);  
   		cnt[i] = count(i);//存下对应的二进制数的1的个数
   	}
   }

   //遍历所有合法的状态
   for (int i = 0; i < st.size(); i++) {
   	for (int j = 0; j < st.size(); j++) {
   		int a = st[i], b = st[j];

   		//如果两个状态之间可以转移，记录进head里
   		if ((a & b) == 0 && check(a | b)) {
   			head[a].push_back(b);
   		}
   	}
   }

   //初始化没有摆出任何国王的方案数是1
   f[0][0][0] = 1;
   for (int i = 1; i <= n+1; i++) {//枚举到i+1行
   	for (int j = 0; j <= m; j++) {//枚举摆放

   		for (auto a : st) {	//枚举所有状态
   			for (auto b : head[a]) {	//枚举出来a能够到达的状态

   				int c = cnt[a];	//取出当前状态的1的个数

   				//如果j足够，即能够由上一层状态转移过来
   				if (j >= c) {
   					f[i][j][a] += f[i - 1][j - c][b];
   				}
   			}
   		}
   	}
   }
   
   //输出摆到n+1行并且n+1行没有摆出，这么最后就不用重新枚举取答案
   cout << f[n + 1][m][0] << endl;

   return 0;
}

AcWing 327. 玉米田

农夫约翰的土地由 $M\times N$ 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 $1$ 行包含两个整数 $M$ 和 $N$。

第 $\mathrm{2..}M+1$ 行：每行包含 $N$ 个整数 $0$ 或 $1$，用来描述整个土地的状况，$1$ 表示该块土地肥沃，$0$ 表示该块土地不育。

输出格式
输出总种植方法对 $10^8$ 取模后的值。

数据范围
$1\le M,N\le 12$
输入样例：

2 3
1 1 1
0 1 0

输出样例：

9

状态表示：$f[i][s]$ 表示已经摆完前i行，且第 $i$ 行的状态是 $s$ 的所有摆放方案的数量

状态计算：

• 每个状态需要满足：状态的二进制表示不能有连续的 $1$。
• 每两层状态之间：(a & b) == 0，即上下不能有连续的 $1$。

假如现在有两个状态：
第一个：已经摆完前 $i$ 行，并且第 $i$ 行的状态是 $a$，第 $i-1$ 行的状态是 $b$。
第二个：已经摆完前 $i-1$ 行，并且第 $i-1$ 行的状态是 $b$。

即第一个状态的方案数量就应该是第二个状态的方案数量，二者是相同的。
状态转移方程为 $f[i][a]+=f[i-1][b]$。

这里对于哪里可以种哪里不能种也需要特殊的判断。
在输入的时候将每一层都变为二进制的形式，并且是不能种的地方为 $1$，能种的地方为 $0$，那么在与任何一个条件进行与运算的时候，如果算出了不为 $0$ 的数，即结果的二进制任何数位上出现了 $1$ ，那么就说明 $1$ 与 $1$ 重叠，即玉米被种到了不能种的地方。

代码：

#include<iostream>
#include<vector>
using namespace std;
const int N = 14, M = 1 << 12;
const int mod = 1e8;

int n, m;
int g[N];
vector<int>st;		//存合法状态（同一层没有相邻1)
vector<int>head[M];	//存能够相互转化的状态
int f[N][M];

bool check(int st) {	//检查是否有相邻的1
	for (int i = 0; i < m; i++) {
		if ((st >> i & 1) && (st >> i + 1 & 1))return false;
	}
	return true;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			int t; cin >> t;

			//如果输入了0，就置为1，然后加2的j次方
			//如果输入了1，就为0
			//实际意义就是：g[i]的二进制数值代表了第i行的状态，且如果为0能放，为1则不能放
			g[i] += !t << j;
		}
	}

	for (int i = 0; i < 1 << m; i++) {	//预处理同层合法状态
		if (check(i))st.push_back(i);
	}

	for (auto i : st) {				//预处理能够转化的状态
		for (auto j : st) {
			if ((i & j) == 0)head[i].push_back(j);
		}
	}

	f[0][0] = 1;
	for (int i = 1; i <= n + 1; i++) {	//枚举层，处理到n+1层
		for (auto s : st) {			//枚举状态

			if (g[i] & s)continue;	//注意这里g[i]是二进制存的状态
			/*如果g[i]&s得到了任何不为0的数，即与运算之后得到的二进制数会有任何一个数位上为1
			* 那就说明这里是与第i层有重叠的1，即有玉米被种到了不育的土地中
			* 那么这种状态应该舍去
			*/

			for (auto b : head[s]) {//枚举能转化到的状态
				f[i][s] = (f[i][s] + f[i - 1][b]) % mod;
			}
		}
	}
	cout << f[n + 1][0];
	return 0;
}

AcWing 292. 炮兵阵地

本题是上一题的扩展，即不仅仅需要考虑前一行了，现在要考虑前两行。

司令部的将军们打算在 N×M 的网格地图上部署他们的炮兵部队。

一个 N×M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式
第一行包含两个由空格分割开的正整数，分别表示 $N$ 和 $M$；
接下来的 $N$ 行，每一行含有连续的 $M$ 个字符( $P$ 或者 $H$ )，中间没有空格。按顺序表示地图中每一行的数据。

输出格式
仅一行，包含一个整数 $K$，表示最多能摆放的炮兵部队的数量。

数据范围
$N\le 100,M\le 10$

输入样例：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例：

6

状态表示：$f[i][j][k]$ 表示所有已经摆完前i行，且第 $i-1$ 行的状态是 $j$，第 $i$ 行的状态是 $k$ 的所有摆放方案的最大数量。

状态计算：
应该满足的条件：

• 三层之间不能有相交的状态：( (a&b) | (a&c) | (b&c) ) == 0
• 炮不能被放到山地上：( g[i - 1] & a | g[i] & b ) == 0

状态转移时，取当前状态和上一层状态转移过来能够放置数量的最大值。
f[i][a][b] = max(f[i][a][b] , f[i-1][c][a] +cnt[b])

存数据时使用滚动数组。

代码：

#include<iostream>
#include<vector>
using namespace std;
const int N = 12, M = 1 << 10;

int n, m;
int g[110];
int cnt[M];
vector<int>st;
int f[2][M][M];	//滚动数组

bool check(int st) {	//检查每一层是不是没有相邻的1
	for (int i = 0; i < m; i++) {
		if ((st >> i & 1) && ((st >> i + 1 & 1) || (st >> i + 2 & 1)))return false;
	}
	return true;
}

int count(int st) {		//计算每个数的二进制状态下有多少个1
	int res = 0;
	for (int i = 0; i < m; i++)res += st >> 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;	//H代表不能放，把这个数位置为1
		}
	}

	for (int i = 0; i < 1 << m; i++) {		//预处理记录合法状态
		if (check(i)) {
			st.push_back(i);
			cnt[i] = count(i);
		}
	}

	for (int i = 1; i <= n + 2; i++) {	//枚举行
		for(auto a : st){				//枚举i-1行状态
			for(auto b : st){			//枚举i行状态
				for(auto c : st){		//枚举i-2行状态
					if ((a & b) | (a & c) | (b & c))continue;
					//如果需要的调节均满足
					if (g[i - 1] & a | g[i] & b)continue;

					//滚动数组更新状态
					//&1之后结果只有0和1
					f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][c][a] + cnt[b]);
				}
			}
		}
	}

	cout << f[n + 2 & 1][0][0];
	return 0;
}

AcWing 524. 愤怒的小鸟

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟， 小鸟们的飞行轨迹均为形如 y=ax2+bx 的曲线，其中 a,b 是 Kiana 指定的参数，且必须满足 a<0。

当小鸟落回地面（即 x 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xi,yi)。

如果某只小鸟的飞行轨迹经过了 (xi, yi)，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过 (xi, yi)，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。

例如，若两只小猪分别位于 (1,3) 和 (3,3)，Kiana 可以选择发射一只飞行轨迹为 y=−x2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个这个游戏。

这些指令将在输入格式中详述。

假设这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

输入格式
第一行包含一个正整数 T，表示游戏的关卡总数。

下面依次输入这 T 个关卡的信息。

每个关卡第一行包含两个非负整数 n,m，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。

接下来的 n 行中，第 i 行包含两个正实数 (xi,yi)，表示第 i 只小猪坐标为 (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。

输出格式
对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

输入样例：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

输出样例：

1
1

如果想要保证能够用最少的小鸟，那么就是要求最少的抛物线穿过最多小猪的数量。
那么本题就是一种重复覆盖问题，即我们需要用最少的行去覆盖最多的列。
也可以说要用最少的抛物线去覆盖最多的状态。

那么就使得 $f[i]$ 表示能够覆盖到 $i$ 状态的最小抛物线数量。

在我们确定了一个抛物线之后去找到其中的没有被覆盖的那一列，之后在保证状态能够覆盖这一列的基础上去枚举其他状态，在当前抛物线最优的情况下就更新为当前抛物线的结果，否则保留其他状态原有的抛物线。

对于本题抛物线，我们仅需求出两点就可以确定出抛物线的方程。

如果我们已经确定了两点$$(x_1,y_1),(x_2,y_2)$$
那么就可得方程：$$\{\begin{array}{l}{a{x}_1}^2+b=y_1\\ {a{x}_2}^2+b=y_2\end{array}$$
如果我们进行以下操作：
$$\{\begin{array}{l}a{x}_1+b=\frac{y_1}{x_1}\\ a{x}_2+b=\frac{y_2}{x_2}\end{array}$$

使得两式相减得到：
$$a\ast (x_1-x_2)=\frac{y_1}{x_1}-\frac{y_2}{x_2}$$

那么我们就能够得到方程未知量关于自变量的关系：
$$a=\frac{\frac{y_1}{x_1}-\frac{y_2}{x_2}}{x_1-x_2}$$
$$b=\frac{y_1}{x_1}-a{x}_1$$

代码:

#include<cstring>
#include<iostream>
using namespace std;

const int N = 18, M = 1 << 18;
const double eps = 1e-8;
#define pdd pair<double,double>
#define x first
#define y second

int n, m;
pdd q[N];		//存点
int path[N][N];	//存抛物线 
int f[M];		//f[i]代表当前已经覆盖的列是i的时候的最小行数

bool com(double a, double b) {	//小数比较
	if (abs(a - b) < eps)return 0;
	if (a < b)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;	//如果只覆盖一个点，那么就先让这个抛物线变为只覆盖i自己

			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 (!com(x1, x2))continue;	//如果相等就跳过

				//公式求
				double a = (y1 / x1 - y2 / x2) / (x1 - x2);
				double b = y1 / x1 - a * x1;

				if (a >= 0)continue;	//遇见a大于等于0的情况也跳过

				int st = 0;	//查看能够覆盖多少点
				for (int k = 0; k < n; k++) {
					double xx = q[k].x, yy = q[k].y;//取出所有点

					//没有能够覆盖到的点就在二进制数位上标记为1
					if (!com(a * xx * xx + b * xx, yy))st += 1 << k;
				}
				path[i][j] = st;//队列中i，j下标对应的点能够确认的抛物线存入path里
			}
		}

		memset(f, 0x3f, sizeof f);

		f[0] = 0;

		//i不能够包含全是1的情况，如果已经覆盖了全部列，就直接跳出
		//枚举所有状态
		for (int i = 0; i + 1 < 1 << n; i++) {
			int xx = 0;

			for (int j = 0; j < n; j++) {//找i状态中没有被覆盖的列
				if ((i >> j & 1) == 0) {
					xx = j;
					break;
				}
			}

			//枚举所有能覆盖到x的抛物线
			for (int j = 0; j < n; j++) {
				//首先xx保证被覆盖，所以或运算之后某些数位一定是被保证了是与path[xx][j]相同的
				//在此基础上去枚举其他状态
				//枚举到其他状态时，如果在当前抛物线的作用下，其他状态采用此方案可以覆盖更多的状态，那么就更新为当前的这个抛物线
				//这里加1是由于在同一列上，一个抛物线肯定只能覆盖到一个点
				//否则的话就保留之前的方案	
				f[i | path[xx][j]] = min(f[i | path[xx][j]], f[i] + 1);
			}

		}
		cout << f[(1 << n) - 1] << endl;//即输出全部列被覆盖的情况
	}

	return 0;
}