状压DP

状态压缩

本节需要比较强的位运算基础素养

有些动态规划需要的状态很多，比如这周第一节我们讲过那个选位置，不能相邻的动态规划问题，因为那个题目只和最后一个位置有关，所以直接设 $d p [i] [0 / 1]$ 就可以解决问题。

但是如果你需要记录多个位置的状态，那就要变成 $d p [i] [0 / 1] [0 / 1] [0 / 1] [0 / 1] \dots \dots$ 了。

这样很明显不好，而且转移的时候会比较麻烦。

我们可以简化一下，如果有 $k$ 个位置的信息需要记录，而且这些信息只有两种状态（其中三种也不是不行），那么你可以把这些位置的信息压缩成一个二进制数字，作为一个状态。

比如如果这里存了一个数字 $37 = (100101)_{2}$ ，那么就表示，你记录的第 $0$ 个位置，第 $2$ 个位置，第 $5$ 个位置已经被占用了。

如果你有 $10$ 个位置要记录，那么这一维要开 $2^{10}$ 的大小（其实也不大，就1024）

P1896 [SCOI2005] 互不侵犯

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

（ 1 <=N <=9, 0 <= K <= N * N）

设 $d p [i] [s] [j]$ 表示，第 $1 \sim i$ 行，已经放了 $j$ 个国王，第 $i$ 行的状态是 $s$ （二进制数）的方案数。

我们设 $s$ 的状态里面有 $k$ 个位置上是 $1$ ，那么就要求：

1、状态 $s$ 里面不能有相邻的 $1$ ，否则会互相攻击

2、设状态 $s$ 里面有 $k$ 个位置上是 $1$

枚举我们从哪个状态转移过来，假如是 $d p [i - 1] [p r e] [j - k]$

那么又要求， $s$ 和 $p r e$ 不能有同一列是 $1$ ，而且两个 $1$ 之间也不能相差仅一列，不然都会互相攻击到。

判断两个二进制数 $s_{1}, s_{2}$ 是否有相邻的位上是 $1$ ，可以判断 $s 1 & s 2$ 以及 $(s_{1} >> 1) & s 2$ 以及 $(s 1 << 1) & s 2$

第一个可以判断没有同一个位置上有 $1$ 。

第二个和第三个可以判断没有相邻位置上都是 $1$ 。

代码总结：

cpp

int n,k;
cin>>n>>k;
int S=(1<<n);//状态上界
for(int s=0;s<S;++s)
{
    int pre=0;
    if(s&(s<<1))
    {
        cnt[s]=-10000;//如果s有相邻两位是1，那么这个状态不合法
        continue;
    }
    for(int k=0;k<n;++k)
    {
        if((s>>k)&1)//如果s的第k位上数字是1
        {
        	++cnt[s];//预处理每个合法状态里面1的个数
        }
    }
    dp[1][s][cnt[s]]=1;//直接处理出第一排的状态。
}
for(int i=2;i<=n;++i)//开始北伐，呃不，转移
{
    for(int s=0;s<S;++s)
    {
        if(cnt[s]<0) continue;//不合法状态
        for(int pre=0;pre<S;++pre)
        {
            if(s&pre) continue;//有并列的
            if(s&(pre<<1)) continue;
            if(s&(pre>>1)) continue;//这两句意思是，相邻的两排有之差一列的。
            for(int j=cnt[s]+cnt[pre];j<=k;++j)//下界可以直接设cnt[s]+cnt[pre]，因为光s和pre里面就有这么多
            {
                dp[i][s][j]+=dp[i-1][pre][j-cnt[s]];
            }
        }
    }
}
int sum=0;
for(int s=0;s<S;++s) sum+=dp[n][s][k];//所有可能的方案都加起来
cout<<sum<<'\n';//爱你