【基础】状压DP - 洛谷保存站

## 刚学完状压DP，写个博客总结一下

------------
### 状压是什么
状压是状态压缩的简称，就是把一种状态变成一个数，但是状态必须是$0,1$组成。“变”的过程就是把这个状态**看成一个二进制数，转成十进制**。

为什么要状压？因为如果用数组存储状态，不但空间放不下，遍历时还会超时，所以用数的状态来存储。

------------
### 状压与DP
用状压结合上DP，其实跟之前用数组存储的DP很像，只是再更改状态时，要用到**位运算**。

状压DP通常用于解决**棋盘问题**，就是在平面上的一个矩形，问里面有几种方法符合要求。

------------
### 举个栗子
**有一排田地，看成$n$个小格，每个小格都可以种田。**

假设$n=6$，这几个小格依次为不种田、种田、种田、不种田、种田、种田，那么：

| 1 | 2 | 3 | 4 | 5 | 6 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 0 | 1 | 1 | 0 | 1 | 1 |

此时，状态就是$(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)
```
$-x$表示将$x$的二进制表示中的所有位取反后加$1$，跟$x$进行&操作后，会发现只有$x$二进制状态下的最右边的$1$还是$1$，其余位全为$0$。（这个是树状数组的$lowbit$函数）

------------
### 例题
[**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)喵！

正在渲染内容...