状压dp小结
状压dp的引入
状压DP，是用二进制的性质来描述状态的一种DP。
对于状压dp，我们要先了解一下位运算。
位运算
x&y与运算，101&110=100x|y或运算，100|101=101x^y异或运算，101^100=001x<<1左移运算x>>1右移运算
状压dp
先看一道题：
在 \(n\times n\) 的棋盘上放 \(k\) 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
对于全部数据，\(1≤n≤10,0≤k≤n^2\)
方法一：爆搜
时间复杂度：\(O(2^{n^2})\)
方法二：状压dp
那dp的状态是什么？
要表示每行的状态，和第几行，是不是要开 dp[11][2][2][2][2][2][2][2][2][2][2]
那就非常麻烦。
于是考虑压维。
我们发现后面的维度都是2，那是不是很像...
二进制！
对，我们可以把后面的维数压成二进制！
然后原先的每个状态现在对应二进制的每一位！
然后我们就能巧妙解决了这个问题！
设 \(dp[i][j][s]\) 表示第 \(i\) 行放置方式为 \(s\) 前 \(i\) 行放置 \(j\) 个国王的方案数。
那，二进制怎么转移啊？
我们发现，国王不能左右攻击，也就是 s&(s<<1)==0
国王不能上下攻击，就是 s&c==0
国王不能斜着攻击，就是 s&(c<<1)=0 和 s&(c>>1)=0
那当满足上述条件的时候，是不是就可以从 \(dp[i-1][j-qiu(s)][c]\) 转移到 \(dp[i][j][s]\) 了？
然后似乎就做出来了。
#include
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<>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< 这道题不够经典，我们来看一道经典题
给出一个由01组成网格，可以在1的位置上放置物品，当放置的东西不能有公共边，问有多少种放法。
\(1≤N,M≤12\)
这题不同的是，有些位置不能放置物品。
那我们可以预处理每一行哪些位置不能放置，记为 \(a_i\)。
然后你在第 \(i\) 行放置的状态 \(s\) 必须满足 s&a_i=0
#include
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<>1))==0) flg[i]=1; //预处理状态
for(i=1; i<=n; ++i) //第几行
for(j=0; j 刚刚的问题我们可以进行更深入的思考。
刚刚的问题的放置影响区域是这样：
那如果是这样呢：
这个问题就变得非常有趣了。
我们不妨加一个状态，由 \(dp[i][j]\) 变成 \(dp[i][j][k]\)，表示上两行的状态。
这样子，我们也可以利用状压dp轻松转移。
但是，这时间复杂度承受得了吗?
表面上看来，状态+转移必然会爆，但实际上并不会。
在一行中放置间隔至少为2的物品，情况非常小。
我们考虑所以数据范围至 \(n\leqslant 100, m\leqslant 10\)，那似乎就能做出这么一道有趣的题了。
#include
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 其实这道题，不仅有这种方法，同样可以压成一维，这就留给读者自己思考。
然而，有些时候，某些题不能压成二进制，是不是就不能用状压dp呢？
我们同样考虑刚刚那类题目，加入状态不是放或不放，而是 \(A,B,C\) 三种状态，那行不行呢？
我们状压dp，是压成二进制。那么此时有三种状态，我们就压成三进制。
实现过程可以参考一下代码：
#include
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 例题
让我们来看一道例题:
[APIO2007] 动物园
给出一个圆环，每个人能看到从某个位置开始连续的五只动物。
对于一个人，如果任意一个自己讨厌的动物被移走，或者任意一个自己喜欢的动物没被移走，那么他就很高兴。
请问最多能使多少人开心。
对于 \(100\%\) 的数据，\(10 \le N \le 10^4\)，\(1 \le C \le 5\times 10^4\)，\(1 \le E \le N\)。
由于动物数和人数很多，明显不能状压，而每个人看到的动物很少，所以可以状压。
由于是个环，我们就先破环成链，设 \(dp[i][j]\) 为从第 \(i\) 个位置开始后五个位置状态为 \(j\) 能使站在前 \(i\) 个位置的人开心的最多数目。
考虑一下这副图：
我们当前枚举的是黄色部分，而我们需要从紫色部分转移过来。
那么对于 \(i-1\) 的那个位置，我们可以枚举它是1或0。
于是我们可以把黄色部分的前面拿出来，变成紫色部分，进行转移。
然而，又有一个问题，环的情况怎么办？
其实，对于环，我们可以枚举初始状态，对于每种初始状态做一次dp。
时间复杂度：\(O(n\times 2^{10})\)
#include
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 以上例题对应一本通提高篇题目。