【基础】状压DP
CatWing
·
·
算法·理论
刚学完状压DP，写个博客总结一下
状压是什么
状压是状态压缩的简称，就是把一种状态变成一个数，但是状态必须是0,1组成。“变”的过程就是把这个状态看成一个二进制数，转成十进制。
为什么要状压？因为如果用数组存储状态，不但空间放不下，遍历时还会超时，所以用数的状态来存储。
状压与DP
用状压结合上DP，其实跟之前用数组存储的DP很像，只是再更改状态时，要用到位运算。
状压DP通常用于解决棋盘问题，就是在平面上的一个矩形，问里面有几种方法符合要求。
举个栗子
有一排田地，看成n个小格，每个小格都可以种田。
假设n=6，这几个小格依次为不种田、种田、种田、不种田、种田、种田，那么：
此时，状态就是(011011)_2，变成十进制等于27，就压缩完毕了~
位运算
这里的位运算都是比较复杂的混合运算，下面给出几个典型的：
1. 判断x二进制下第i位是不是等于1（最低第1位）
if(((1 << (i − 1)) & x) > 0)
将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数，然后与x做&运算，如果结果>0，说明x第i位上是1，反之则是0。
2. 将x二进制下第i位更改成1
x = x | (1 << (i − 1))
制造了一个只有第i位上是1，其他位上都是0的二进制数，然后用x和它作|操作，显然，第i位必定变成1，其余位不变。
3. 将x二进制下第i位更改成0
x = x & ~(1 << (i − 1))
构造了一个前i位只有第i位为0，其余为是1的二进制数，然后和x进行&操作，显然第i为变为0。
4. 把x二进制下最靠右的第一个1去掉
x = x & (x − 1)
二进制下的x-1的最右边的1必定变成0，再进行&操作，就使x末尾的1成了0。
5. 计算x的二进制表示中最低位为1的位
x & (-x)
------------
### 例题
[**P1879**](https://www.luogu.com.cn/problem/P1879)
形式化题面：给出$n×m$的棋盘，每个格子不是$0$就是$1$，$1$代表可以种草，否则不能。**相邻两个格子不能同时种草**，求种草的方案总数。
首先，我们确定用来DP的数组是什么：$f[i][j]$表示第$i$行状态为$j$时的方案数。
其次，辅助数组很重要，此题需要一个**存储每行能否种草的状态**的数组$a$，$a[i]$就是当前行的状态看成二进制后转化成的十进制数；还有数组$c$，$c[i]$的值是$1$**表示一行有$i$个草时，草可以两两不相邻**，反之则不满足要求。
接着，**初始化**，设$b$是一行每个格子**都种草**这个状态，所代表的值。初始化$a[0]=b$，然后输入，如果第$i$行第$j$列能种草，就把$a[i]$**二进制形式下的第$j$为变为$1$**。（这里所有的混合位运算都不作讲解，往上翻）初始化数组$c$，$i$从$0$遍历到$b$，如果一行有$i$个草的情况下能满足草两两不相邻，$c[i]=1$。$f[0][0]$表示第$0$行有$0$个草的方案数，等于$1$。
然后，开始DP，$i$遍历行，$j$遍历当前行的状态，**如果这一行的种草情况可以种$j$这种状态，且$c[j]$是$1$**，遍历上一行的状态（$0≤k≤b$），**如果$k$和$j$这两个数在二进制状态下没有两个相同的数位都为$1$，表示第$i$行和第$i-1$行没有上下相邻的草**，就让$f[i][j]$加上$f[i-1][k]$（上一行的方案数），不要忘了模$mod$。
最后，DP完毕，用$ans$记录结果。$i$遍历每个状态，$ans$每次加上$f[n][i]$（**最后一行是所有状态的结果**），每次也要模$mod$，输出，**完结撒花！！！**
代码在下面，有注释↓
```
#include <bits/stdc++.h>
using namespace std;
int a[13],c[1 << 13];//a表示每一行土地的状态，c表示当前行是否满足草无相邻
long long f[13][1 << 13],mod = 1e8;//f就是用来DP存储结果的数组
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int b = (1 << m) - 1;//b表示满草状态
a[0] = b;//第0行设初值为满草
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
int x;
scanf("%d",&x);
if(x != 0)//如果第i行j列有草
{
a[i] |= (1 << (j - 1));//就把a[i]的二进制情况下的第j位设为1
}
}
}
for(int i = 0;i <= b;i++)
{
c[i] = (((i << 1) & i) == 0);//判断草为状态i的情况下是否满足草不相邻
}
f[0][0] = 1;//初值
for(int i = 1;i <= n;i++)//遍历行
{
for(int j = 0;j <= b;j++)//遍历草的状态
{
if((a[i] & j) == j && c[j] == 1)//j里的1被a[i]里的1全部覆盖，且c[j]为1
{
for(int k = 0;k <= b;k++)//枚举上一行状态
{
if((k & j) == 0)//加上其中和j不覆盖的值（因为上下相邻的两格也不能都有草）
{
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;//加上一行的情况数
}
}
}
}
}
long long ans = 0;
for(int i = 0;i <= b;i++)//枚举所有状态
{
ans = (ans + f[n][i]) % mod;//加上第n行草状态i的情况数，每次都要%mod
}
printf("%lld",ans);//AC撒花！
return 0;
}
```
（又种玉米又种草的我想干啥，不如种“一个草”吧……）
------------
### 总结
状压DP可以分为以下几步：
1. 保存每行状态
2. 初始化，判断每个状态是否可行
3. **开始DP，先遍历行，再遍历状态，如果满足要求，再次遍历状态，与上一行判断一下，如果还符合要求，就用这一行的方案数，加上上一行的**
4. 输出最后一行每种情况的方案数之和
有的时候，题目看起来跟DP没有一点关系，我们就需要**把样例先写出来，再尝试用列表的方式写，找上下两行的关系**，就会发现跟DP挂上钩了。
------------
> 进阶篇请见[这里](https://www.luogu.me/article/34caw9rs)喵！