本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15825535.html

状压dp的引入

状压DP，是用二进制的性质来描述状态的一种DP。

对于状压dp，我们要先了解一下位运算。

位运算

  • x&y 与运算，101&110=100
  • x|y 或运算，100|101=101
  • x^y 异或运算，101^100=001
  • x<<1 左移运算
  • x>>1 右移运算

状压dp

先看一道题：

在 n×nn\times n 的棋盘上放 kk 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
对于全部数据，1≤n≤10,0≤k≤n21≤n≤10,0≤k≤n^2

方法一：爆搜

时间复杂度：O(2n2)O(2^{n^2})

方法二：状压dp

那dp的状态是什么？

要表示每行的状态，和第几行，是不是要开 dp[11][2][2][2][2][2][2][2][2][2][2]

那就非常麻烦。

于是考虑压维。

我们发现后面的维度都是2，那是不是很像…

二进制！

对，我们可以把后面的维数压成二进制！

然后原先的每个状态现在对应二进制的每一位！

然后我们就能巧妙解决了这个问题！

设 dp[i][j][s]dp[i][j][s] 表示第 ii 行放置方式为 ss 前 ii 行放置 jj 个国王的方案数。

那，二进制怎么转移啊？

我们发现，国王不能左右攻击，也就是 s&(s<<1)==0

国王不能上下攻击，就是 s&c==0

国王不能斜着攻击，就是 s&(c<<1)=0 和 s&(c>>1)=0

那当满足上述条件的时候，是不是就可以从 dp[i−1][j−qiu(s)][c]dp[i-1][j-qiu(s)][c] 转移到 dp[i][j][s]dp[i][j][s] 了？

然后似乎就做出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, i, j, k; 
int dp[15][150][1050]; 
int ans, a, b; 

int qiu(int x) //求这个状态有多少个国王 
{
	int ans=0; 
	while(x) ++ans, x-=x&-x; 
	return ans; 
}

signed main()
{
	scanf("%lld%lld", &n, &k); 
	for(i=0; i<(1<<n); ++i)
		if((m=qiu(i))<=k && !(i&(i<<1)))
			dp[1][m][i]=1; //初始化第一行
	for(i=2; i<=n; ++i) //第几行 
		for(a=0; a<(1<<n); ++a) //这一行状态 
			for(b=0; b<(1<<n); ++b) //上一行状态 
				if(!(a&b) && !(a&(b<<1)) && !(a&(b>>1)) && !(b&(b<<1))) //不互相攻击 
					for(j=(m=qiu(b))+qiu(a); j<=k; ++j) //放置国王个数 
						dp[i][j][b]+=dp[i-1][j-m][a]; 
	for(i=0; i<(1<<n); ++i) ans+=dp[n][k][i]; //计算答案 
	printf("%lld", ans); 
	return 0;
}

这道题不够经典，我们来看一道经典题

给出一个由01组成网格，可以在1的位置上放置物品，当放置的东西不能有公共边，问有多少种放法。
1≤N,M≤121≤N,M≤12

这题不同的是，有些位置不能放置物品。

那我们可以预处理每一行哪些位置不能放置，记为 aia_i。

然后你在第 ii 行放置的状态 ss 必须满足 s&a_i=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mo 100000000
#define N 15
#define M 100010
int n, m, i, j, k; 
int a[N], f[N][M], ans; 
int flg[M], maxx; 

signed main()
{
	scanf("%lld%lld", &n, &m); 
	for(i=1; i<=n; ++i)
		for(j=1; j<=m; ++j) 
			scanf("%lld", &k), a[i]=(a[i]<<1)+k; //预处理每一行是否能放 
	f[0][0]=1; maxx=(1<<m); 
	for(i=0; i<maxx; ++i) 
		if((i&(i<<1))==0&&(i&(i>>1))==0) flg[i]=1; //预处理状态 
	for(i=1; i<=n; ++i) //第几行 
		for(j=0; j<maxx; ++j) //这一行状态 
			if((j&a[i])==j&&flg[j]) //满足可以放 
				for(k=0; k<maxx; ++k) //上一行状态 
					if((j&k)==0) f[i][j]=(f[i][j]+f[i-1][k])%mo; 
	for(i=0; i<(1<<m); ++i) ans=(ans+f[n][i])%mo; //统计答案 
	printf("%lld", ans); 
	return 0;
}

刚刚的问题我们可以进行更深入的思考。

刚刚的问题的放置影响区域是这样：
image
那如果是这样呢：
image

这个问题就变得非常有趣了。

我们不妨加一个状态，由 dp[i][j]dp[i][j] 变成 dp[i][j][k]dp[i][j][k]，表示上两行的状态。

这样子，我们也可以利用状压dp轻松转移。

但是，这时间复杂度承受得了吗?

表面上看来，状态+转移必然会爆，但实际上并不会。

在一行中放置间隔至少为2的物品，情况非常小。

我们考虑所以数据范围至 n⩽100,m⩽10n\leqslant 100, m\leqslant 10，那似乎就能做出这么一道有趣的题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, i, j, k; 
int dp[3][1025][1025]; 
int ans, u, a[110]; 
char s[15]; 

int check(int x, int i)
{
	if(((x&(x<<1)) || (x&(x<<2)))) return 1; 
	if((x|a[i])!=a[i]) return 1; 
	return 0; 
}

int suan(int x)
{
	int ans=0; 
	while(x) ++ans, x-=x&-x; 
	return ans; 
}

signed main()
{
	memset(dp, -1, sizeof(dp)); 
	scanf("%lld%lld", &n, &m); 
	for(i=1; i<=n; ++i)
	{
		scanf("%s", s); 
		for(j=0; j<m; ++j)
			a[i]|=((s[j]=='P' ? 1 : 0)<<j); 
	}
	for(i=0; i<(1<<m); ++i)
	{
		if(check(i, 2)) continue; 
		for(j=0; j<(1<<m); ++j)
			if(!check(j, 1) && (i&j)==0) dp[0][i][j]=suan(i)+suan(j); 
	}
	for(i=3; i<=n; ++i)
		for(j=0; j<(1<<m); ++j)
		{
			if(check(j, i)) continue; 
			for(k=0; k<(1<<m); ++k)
			{
				if(check(k, i-1) || (j&k)) continue; 
				for(u=0; u<(1<<m); ++u)
				{
					if(check(u, i-2) || (k&u) || (j&u)) continue; 
					dp[i%2][j][k]=max(dp[i%2][j][k], suan(j)+dp[(i-1)%2][k][u]); 
				}
			}	
		}
	for(i=0; i<(1<<m); ++i)
	{
		if(check(i, n)) continue; 
		for(j=0; j<(1<<m); ++j)
			if((!check(j, n-1)) && ((i&j)==0)) ans=max(ans, dp[n%2][i][j]); 
	}
	printf("%lld", ans); 
	return 0;
}

其实这道题，不仅有这种方法，同样可以压成一维，这就留给读者自己思考。

然而，有些时候，某些题不能压成二进制，是不是就不能用状压dp呢？

我们同样考虑刚刚那类题目，加入状态不是放或不放，而是 A,B,CA,B,C 三种状态，那行不行呢？

我们状压dp，是压成二进制。那么此时有三种状态，我们就压成三进制。

实现过程可以参考一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
#define mo 1000000
int n, m, i, j, k, p; 
int f[N], dp[N], t[N]; 

int check(int x)
{
	for(int i=1; i<m; ++i)
	{
		if(x%3==x/3%3) return 0; 
		x/=3; 
	}
	return 1; 
}

int pan(int x, int y)
{
	for(int i=1; i<=m; ++i, x/=3, y/=3)
		if(x%3==y%3) return 0; 
	return 1; 
}

int suan(int x)
{
	if(x==0) return 1; 
	memset(f, 0, sizeof(f)); 
	f[j]=1; 
	int i, j, k; 
	for(k=1; k<=x; ++k)
	{
		for(i=0; i<t[m]; ++i)
			if(check(i))
				for(j=0; j<t[m]; ++j)
					if(check(j) && pan(i, j))
							dp[i]+=f[j]; 					
		for(i=0; i<t[m]; ++i) f[i]=dp[i]%mo, dp[i]=0; 
	}
	for(i=k=0; i<t[m]; ++i) k+=f[i]; 
	return k%mo; 
}

signed main()
{
	scanf("%lld%lld%lld", &n, &m, &k); 
	for(i=t[0]=1; i<=10; ++i) t[i]=t[i-1]*3%mo; 
	for(i=1; i<=m; ++i) scanf("%lld", &p), j+=t[i-1]*(p-1); 
	printf("%lld", suan(k-1)*suan(n-k)%mo); 
	return 0;
}

例题

让我们来看一道例题:

[APIO2007] 动物园

给出一个圆环，每个人能看到从某个位置开始连续的五只动物。

对于一个人，如果任意一个自己讨厌的动物被移走，或者任意一个自己喜欢的动物没被移走，那么他就很高兴。

请问最多能使多少人开心。

对于 100%100\% 的数据，10≤N≤10410 \le N \le 10^4，1≤C≤5×1041 \le C \le 5\times 10^4，1≤E≤N1 \le E \le N。

由于动物数和人数很多，明显不能状压，而每个人看到的动物很少，所以可以状压。

由于是个环，我们就先破环成链，设 dp[i][j]dp[i][j] 为从第 ii 个位置开始后五个位置状态为 jj 能使站在前 ii 个位置的人开心的最多数目。

考虑一下这副图：

image

我们当前枚举的是黄色部分，而我们需要从紫色部分转移过来。

那么对于 i−1i-1 的那个位置，我们可以枚举它是1或0。

于是我们可以把黄色部分的前面拿出来，变成紫色部分，进行转移。

然而，又有一个问题，环的情况怎么办？

其实，对于环，我们可以枚举初始状态，对于每种初始状态做一次dp。

时间复杂度：O(n×210)O(n\times 2^{10})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std; 
#define int long long
int n, m, i, j, k; 
int dp[10010][50]; 
int f[10010][50]; 
int p, ans, l, r, e; 
int a, b; 

int du()
{
	int x; scanf("%lld", &x); 
	if(x<e) x+=n; 
	return x-=e; 
}

int check(int x, int a, int b)
{
	if(x&b) return 1; 
	if((~x)&a) return 1; 
	return 0; 
}

signed main()
{
	memset(dp, 0x80, sizeof(dp)); 
	scanf("%lld%lld", &n, &m); 
	for(i=1; i<=m; ++i)
	{
		scanf("%lld%lld%lld", &e, &l, &r); 
		b=0; a=0; 
		for(j=1; j<=l; ++j) a|=(1<<du()); 
		for(j=1; j<=r; ++j) b|=(1<<du()); 
		for(j=0; j<32; ++j) f[e][j]+=check(j, a, b); 
	}
	for(p=0; p<32; ++p)
	{
		memset(dp[0], 0x80, sizeof(dp[0])); 
		dp[0][p]=0; 
		for(i=1; i<=n; ++i) 
			for(j=0; j<32; ++j)
				dp[i][j]=max(dp[i-1][(j&15)<<1], dp[i-1][(j&15)<<1|1])+f[i][j]; 
		ans=max(ans, dp[n][p]); 
	}
	printf("%lld", ans); 
	return 0;
}

以上例题对应一本通提高篇题目。