题解 P1896 [SCOI2005]互不侵犯

暗ざ之殇 · 2019-11-05 15:42:13 · 题解

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

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

闲话时刻：

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

所以状压 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 ；

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

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

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

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

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

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

更短的写法：

所以我们下一步的状态 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 终究是上一行的状态 ，是一定已经被算过的了，这就保证了不重不漏!