自动搬运

查看原文

来自洛谷，原作者为

	暗ざ之殇 你要记得，紫檀未灭，我亦未去。

搬运于2025-08-24 21:31:38，当前版本为作者最后更新于2019-11-05 15:42:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

做完后的一点体会，希望能帮助和我一样不熟练状压 dp 的萌新

写得挺详细的，对萌新极为友好

闲话时刻：

日常打开洛谷，看了一眼智能推荐题目：

$1896 [SCOI2005]$互不侵犯？

水题啊！ 嗯，一道状压 $dp$ 好题，之前老早就想做了，正好练练状压 $dp$，于是就开始做了起来；

题目大意：

一般来说题目越短越难。

在一个 $n * n$ 的图中选 $k$ 个点，使得以每个点为中心的九宫格内有且只有它一个点，问方案数；

题解：

一道很好的状压 $dp$ 练手题；

状压状压，就是把一种状态压缩成一个数，达到节省空间的目的；

举个栗子：

假设我们有一行是这样放的国王（红色位置表示放国王）：

正常操作：我们可以开一个一维数组 $f [ i ]$ 表示第 $i$ 个位置有没有放上国王；

状压操作：

上面的渣渣真是费空间，看我的！

由于每个格子只有两种状态：放国王 和 不放国王 ，所以我们可以用 $1$ 表示放国王，$0$ 表示不放国王；

那么把每个格子的数连起来就是：

这是什么？如果我们将这个$01$串看成是一个二进制数的话，那么这种状态就被我们完美的表示成了一个数，这个数在十进制下是：$(101001)_2$ $=$ $( 41)_{10}$

所以状压 $dp$ 的套路就是不断的去枚举表示状态的数，去转移即可。

状态设置：

按照状压 $dp$ 的套路，我们设状态：$dp [ i ][ j ][ S ]$ 表示我们已经选到了第 $i$ 行，第 $i$ 行的状态为 $S$，用了 $j$ 个国王的方案数；

转移方程：

首先看一下国王的攻击范围（以其为中心的九宫格）：

红色代表国王位置，蓝色代表它的攻击范围：

思考：如果我们第 $i-1$ 行的第 $j$ 列放好国王之后，那么对第 $i$ 行的影响是什么呢？

也就是国王在第 $i$ 行上的攻击范围内的格子不能再放国王了：

也就是说，如果第 $i-1$ 行的状态 $S_1$（表示状态的二进制数）的第 $j$ 位是 $1$（放国王）的话，第 $i$ 行的状态 $S_2$ 的第 $j-1$，$j$，$j+1$ 位一定为 $0$（不能再放国王了），否则就是不合法的状态；

那怎么表示这一条件呢？回归到二进制上来看：

假如我们现在正在决定第 $i$ 行的状态：

显然这个红色的 $1$ 是不合法的，但是怎么知道它是不合法的呢？

这里就要运用巧妙的位运算了：

此时 $S_1$ & $S_2 ≠ 0$；

那如果是右下方有一个国王呢？

我们可以按照刚刚那样的方法用位运算：

$1.$ 先将 $S_2$ 向左移一位：

$2.$ 然后这样两个 $1$ 就冲齐了，此时两种状态的 & 运算是不为 $0$ 的；

$(S_2<<1)$ & $S_1 ≠ 0$；

在左下方的情况同理：

$1.$ 我们先将 $S_2$ 向右移一位：

$2.$ 然后发现此时两状态的 & 运算不为 $0$；

$(S_2>>1)$ & $S_1 ≠ 0$；

所以我们就得出了表示这三个位置的方法，那么 $S_2$ 必须满足什么条件才可能由 $S_1$ 转移过去呢？

条件：$( S_2$ & $S_1$ $== 0 )$ && $( ( S_2<<1 )$ & $S_1 ) == 0 )$ && $( ( S_2>>1 )$ & $S_1 == 0 )$

我们发现这样写有点长，还可以这样写哦：

$( S_2 | ( S_2>>1 ) | ( S_2<<1 ) )$ & $S_1 ==0$

当然，我们处理完行间的限制后，接下来就要处理行内的限制了；

一个国王的左右格子内不能再放国王了，这就是行内的限制！

运用上面的第二，三种情况的做法，问题就迎刃而解了：

$1.$ 判断左边有没有国王：

我们将 $S_2$ 向右移一位，再与原来的 $S_2$ 做 & 运算：

观察到 $1$ 左边的数右移后跑到了 $1$ 的位置上，所以我们再做一次 & 运算即可：

若结果为 $0$ ，说明那一位是 $0$（合法）；否则为 $1$（不合法）；

$2.$ 判断右边有没有国王：

同理，将 $S_2$ 左移一位再做 & 运算：

把上述过程转化成代码：

$( ( S_2<<1 )$ & $S_2 ==0 )$ && $( ( S_2>>1 )$ & $S_2 ==0 )$

更短的写法：

$( ( S_2<<1 ) | ( S_2>>1 ) )$ & $S_2 ==0$

所以我们下一步的状态 $S_2$ 要同时满足这两个条件才可以哦~

因为第二个条件只与状态的情况有关，所以我们可以预处理这个东西，$dp$ 的时候将所有满足第二条性质的状态拿出来看看是否再满足第一条性质就好了；

考虑第二维怎么转移的：

显然对于第 $i-1$ 行来说，第 $i$ 行多放的国王数就是第 $i$ 行的状态上 $1$ 的个数（在二进制下）；

综上，则有 $dp [ i ][ j ][ S_2 ] += dp [ i-1 ][ j-cnt [ S_2 ] ][ S_1 ]$ ，（其中 $S_2$ 要满足上述两个条件，$cnt [ S_2 ]$ 表示 $S_2$ 在二进制下有几个 $1$）

发现转移方程类似于背包 $dp$ 时的方程

边界设置

刚开始一个偌大的棋盘，我们啥也不知道，只知道它的第 $0$ 行不能放旗子（先说有第 $0$ 行嘛$qwq$）；

即 $dp [ 0 ][ 0 ][ 0 ] = 1$；

答案输出

最后的情况，肯定是我们已经考虑完 $n$ 行的排放情况，并且在其中一定是只放了 $k$ 个国王了，但对于第 $n$ 行具体摆成什么稀奇古怪的亚子，我们也不知道，所以我们去枚举第 $n$ 行所有可能的情况，统计答案就好了；

细节提示

最后注意开 $long long$ 哦~，不然随时见到你的祖宗

完整代码（详细注释版）：

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,num;
long long cnt[2000],ok[2000];   
//cnt[i]:第i种状态的二进制中有几个1
//ok[i]:第i个行内不相矛盾(满足条件2:左右国王不相邻)的状态是多少 
long long dp[10][100][2000];
//dp[i][j][s]:我们已经放了i行,用了j个国王,第i行的状态为s的方案数
int main() 
{
    cin>>n>>k;                    //n*n的棋盘上放k个国王 
    for(int s=0;s<(1<<n);s++)     //枚举所有可能状态 
    {
        int tot=0,s1=s;           //tot:二进制下有多少个1; 
        while(s1)                 //一位一位枚举,直至为0(做法类似于快速幂那样) 
        {
            if(s1&1) tot++;       //如果最后一位是1,tot++ 
            s1>>=1;               //右移看下一位 
        }
        cnt[s]=tot;               //预处理这个二进制数有多少个1
        if((((s<<1)|(s>>1))&s)==0) ok[++num]=s; //如果这一状态向左向右都没有重复的话,说明左右不相邻,合法 
    }
    dp[0][0][0]=1;                //第0行一个也不放的方案数
    for(int i=1;i<=n;i++)         //枚举我们已经放到了第几行 
    {
        for(int l=1;l<=num;l++)   //枚举第i行的状态,这里我们直接枚举所有满足条件2的状态,算是个优化吧 
        {
            int s1=ok[l];             
            for(int r=1;r<=num;r++) //枚举上一行的状态 
            {
                int s2=ok[r];
                if(((s2|(s2<<1)|(s2>>1))&s1)==0)  //如果上下,左下右上,左上右下方向都不相邻,合法 
                {    
                       for(int j=0;j<=k;j++) //枚举国王个数 
                        if(j-cnt[s1]>=0)  
                            dp[i][j][s1]+=dp[i-1][j-cnt[s1]][s2];  //状态转移方程       
                }
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=num;i++) ans+=dp[n][k][ok[i]];  //枚举第n行所有可能的情况,统计答案 
    printf("%lld\n",ans);    //输出 
    return 0;
}

做题的道路并不是一帆风顺的，博主在做题的时候对 $dp$ 的枚举顺序一直不是很明白，听了 $qyf$ 神仙的讲解后才豁然开朗，在此感谢一下 $qyf$ 神仙；

在此我再将 $qyf$ 神仙的解释以我的理解说一下吧，帮助一下有同样困惑的 $Oier$：

一开始我的顺序是这样的：

for(int l=1;l<=num;l++)   //第i行的状态 
{
    int s1=ok[l]; 
    for(int r=1;r<=num;r++) //第i-1行的状态 
    {
        int s2=ok[r]; 
        if(((s2|(s2<<1)|(s2>>1))&s1)==0) 
        {    
            for(int i=1;i<=n;i++)  //枚举选到了哪一行 
                for(int j=0;j<=k;j++)  //枚举国王个数 
                    if(j-cnt[s1]>=0)  
                        dp[i][j][s1]+=dp[i-1][j-cnt[s1]][s2];    
        }
    }
}

错误的原因：

我们注意到在 $dp$ 过程中我们是按照状态从小到大去枚举的，所以 $dp$ 数组的赋值顺序是按照 $S_1$ 和 $S_2$ 从小到大来依次赋值的，换句话说，哪一个状态转化成十进制的数越小，它所对应的 $dp$ 值越先被赋值；但是在 $dp$ 过程中， 上一行的状态 $S_2$ 是有可能比当前行状态 $S_1$ 要大的，但是因为我们现在正在给 $S_1$ 所对应的状态赋值，所以比 $S_1$ 还大的 $S_2$ 固然还没有被赋值，所以这就漏掉了好多情况，导致答案偏小；

正确写法：

我们先枚举 $i$，再枚举状态 。这样的话就是按照所选的行来转移，即使 $S_2$ 再比 $S_1$ 大，但 $S_2$ 终究是上一行的状态 ，是一定已经被算过的了，这就保证了不重不漏!