P1869 互不侵犯题解

题目传送门

思路

对于每一行，我们可以将它设置为一个状态。

比如这一行：

（红的是国王，白的为空）

假设空的为 $0$ ，国王为 $1$ ，那么这一行的状态就可以表示为 $0100101$ 。

把 $0100101$ 看作是一个二进制数，那么它的十进制为 $37$ 。

我们不需要存储 $0100101$ ，只存储 $37$ 即可。这就是本题状态压缩的思路。

因此我们称这一行的状态为 $37$ 。

根据题意可得，当一行内没有相邻的国王时，这一行就成立。

那么，我们如何判断一个状态是否成立呢？

不难想到，可以 $\mathcal{O}(n)$ 枚举，但这样速度太慢。

那么，我们就要用到下面几个位运算。

a & b：按位与。当二进制数 $a$ 与 $b$ 不存在同一位都为 $1$ ，结果就为 $0$ 。
a << 1：左移。将二进制数 $a$ 的所有位置上的数字向左移动一位。
a >> 1：右移。将二进制数 $a$ 的所有位置上的数字向右移动一位。

假设此行的状态为 $a$ 。（ $a$ 是一个二进制数）

我们先将 $a$ 左移一位，再与原始的 $a$ 对齐

1 2	原始的a： a[1] a[2] a[3] 左移一位后的a：a[1] a[2] a[3] a[4]...

这样，我们就把 $a_i$ 和 $a_{i+1}$ 对齐了。

将这两个数进行按位与运算。

如果返回值为 $0$ ，说明不存在 $a_i$ 和 $a_{i+1}$ 都为 $1$ 的情况。

所以可得，当 (a&(a<<1))==0)时，状态 $a$ 成立。

再思考，什么条件下，上面一行的状态为 $s1$ ，下面一行的状态为 $s2$ ，且上下不冲突。

假设上面一行的第 $i$ 位为 $1$ ，那么下面一行的第 $i-1$ 、 $i$ 、 $i+1$ 位都不能是 $1$ 。

$~$

先将 $s1$ 与 $s2$ 对齐

1 2	s1：s1[1] s1[2] s1[3] s1[4]... s2：s2[1] s2[2] s2[3] s2[4]...

此时 $s1_i$ 与 $s2_i$ 对齐。

将 $s1$ 与 $s2$ 进行按位与运算。如果返回值为 $0$ ，就说明不存在 $s1_i$ 与 $s2_i$ 都为 $1$ 。

$~$

再将 $s1$ 与左移一位的 $s2$ 对齐。

1 2	s1： s1[1] s1[2] s1[3]... s2：s2[1] s2[2] s2[3] s2[4]...

此时 $s1_i$ 与 $s2_{i+1}$ 对齐

将 $s1$ 与左移一位的 $s2$ 进行按位与运算。如果返回值为 $0$ ，就说明不存在 $s1_i$ 与 $s2_{i+1}$ 都为 $1$ 。

$~$

最后将 $s1$ 与右移一位的 $s2$ 对齐。

1 2	s1：s1[1] s1[2] s1[3] s1[4]... s2： s2[1] s2[2] s2[3]...

此时 $s1_i$ 与 $s2_{i-1}$ 对齐

将 $s1$ 与右移一位的 $s2$ 进行按位与运算。如果返回值为 $0$ ，就说明不存在 $s1_i$ 与 $s2_{i-1}$ 都为 $1$ 。

$~$

如果上面的三个条件都满足，就说明：当 $s1_i=1$ 时， $s2_{i-1}$ 、 $s2_{i}$ 、 $s2_{i+1}$ 都不为 $1$ 。

所以可得，当 (s1&s2==0)&&(s1&(s2<<1))==0)&&((s1&(s2>>1))==0)时， $s1$ 与 $s2$ 不冲突。

接下来推转移方程式.

假设 $dp[i][j][k]$ 表示第 $i$ 行，使用了 $j$ 个国王，此行的状态为 $k$ 的方案数。

那么，若现在为第 $i$ 行，使用了 $l$ 个国王，当前行状态为 $s2$ ，上一行状态为 $s1$ ，转移方程就是 dp[i][l][s2]+=dp[i-1][l-cnt_king[s2]][s1];

注：cnt_king[s2] 为状态为 $s2$ 的国王个数。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int cnt_king[3000];
int dp[10][100][3000];
vector<int> p;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<(1<<n);i++)//枚举每一个状态，状态数量为 2^n 个
    {
        int x=i,res=0;//res:状态为i时，国王的个数
        while(x)
        {
            x-=(x&-x);//减去最低位的1
            res++;
        }
        cnt_king[i]=res;
        if(((i&(i<<1))==0)) p.push_back(i);//判断i是否合法。如果合法，就加入p里
    }
	
    dp[0][0][0]=1;
	
    for(int i=1;i<=n;i++)//当前是第i行
    {
        for(int j=0;j<p.size();j++)//枚举当前行的状态
        {
            int s2=p[j];
            for(int m=0;m<p.size();m++)//枚举上面行的状态
            {
                int s1=p[m];
                if(!(((s1&s2)==0)&&((s1&(s2<<1))==0)&&((s1&(s2>>1))==0))) 
                    continue;//如果不合法，就直接跳过
					
                 for(int l=cnt_king[s2];l<=k;l++) //遍历国王个数
                    dp[i][l][s2]+=dp[i-1][l-cnt_king[s2]][s1];//转移方程
            }
        }
    }
    int ans=0;
    for(int i=0;i<p.size();i++) 
        ans+=dp[n][k][p[i]];//将最后一行，国王个数为k，所有状态的方案数相加
    cout<<ans;
    return 0；
}