题解 P1896 【[SCOI2005]互不侵犯】

Ykimna

2019-10-26 11:25:32

题解

需要强调一点：状压dp也是 dp,需要普通动态规划基础，如没有普通动态规划基础还是先去巩固基础更为重要。

我也不知道我是否能讲清楚，如果哪里有疑问可以评论，或私信我（我在退役之前都能回答你）

前置知识：普通动态规划，位运算。

这道题题意非常简单就不再赘述，直接来讲讲数据处理方法。 如果一般的动态规划去想这道题，你会发现它的状态很难去表示和转移（ 当然你也可以去开个10维数组 ），这就需要引入一种方法去表示它的状态，我们可以用一个数来表示它的状态，这个数每位只有两个数0或1，对于这道题来说1为国王，0为空格。

比如：10101 表示的就是：

很显然如果棋盘有9格那么这个数会到1e8数组会炸，所以我们就需要用个方法来减维，那就是 状压 。因为这个数每位只0或1，那么很显然我们可以用二进制来表达这个状态，再把这个二进制转化为十进制来存储，1e8就就会退化为 \log_21e8 最大也就为 2^9-1(511) 。这样就可以用数组存下了。

接下来就来讲一下思路：我们先来处理每一行棋盘的所有合法状态。根据题意每个国王的左右不能有国王也就是只能插空站，在判断国王是否相邻（状态是否合法）有一种简单的方法 & 运算。这里举两个例子。

  1. 10101

我先把这个数左移一位再与这个数进行 & 运算

  1. 11010

我们发现合法序列的在计算后的值为 0 ，而不合法的序列计算后的值不为 0 。因此我们就可一从0枚举到 2^n-1 把所有的合法序列存在 sta[N] 数组里面。同时我们可以用 king[N] 数组把每一个合法状态有多少个国王存下来。

代码如下：

int cnt=0;
for(int i=0;i<=(1<<n)-1;i++)
{
    if(i&(i<<1)) continue;
    sta[++cnt]=i;int gw=i; //存合法状态
    while(gw>0)//计算国王数量
    {
        if(gw%2==1) king[cnt]++;
        gw>>=1;
    }
}

之后的大致思路就是比较所有 X 行和 Y 行，其中 X 为 Y 的上一行，也就是说 X=Y-1 ，枚举所有 X 行和 Y 行的所有合法状态再计算出这 两排 的合法状态，因为想要整个棋盘合法，就要每一行棋盘都要与其上下两行棋盘合法 也就是国王的上方，左上，右上和下方，左下，右下都不能为国王。比较方法如下：

    if(sta[j]&sta[k]) continue;//j枚举的是Y行的合法状态，k为X行的合法状态
    if((sta[j]<<1)&sta[k]) continue;
    if(sta[j]&(sta[k]<<1)) continue;

判断合法的状态都讲了，就可开始dp了，我们定义一个dp[i][j][k]数组，前i行，状态为j，使用了k个国王时的总方案数。再前文枚举X和Y合法后，我们就再枚举国王数就可以了。代码如下

for(int c=0;c<=ki;c++)
{
    if(king[j]+c>ki) break;
    dp[i][j][king[j]+c]+=dp[i-1][k][c];
}

细节：处理好位运算的优先级，还有就是 十年OI一场空，不开long long见祖宗

下面贴完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<10)+20;
const int M=17;
int n,ki,cnt,king[N];
long long ans,sta[N],dp[M][N][M*M];
int main()
{
    cin>>n>>ki;
    for(int i=0;i<=(1<<n)-1;i++)
    {
       if(i&(i<<1)) continue;
       sta[++cnt]=i;int gw=i; //存合法状态
       while(gw>0)//计算国王数量
       {
          if(gw%2==1) king[cnt]++;
          gw>>=1;
       }
    }
    for(int i=1;i<=cnt;i++)//初始化第一排，因为我们枚举的是X与X-1行
        if(king[i]<=ki) //一行的国王数不可能超过国王的总数量
            dp[1][i][king[i]]=1;
    for(int i=2;i<=n;i++)//枚举每行
    {
        for(int j=1;j<=cnt;j++)//X行的合法状态
        {
            for(int k=1;k<=cnt;k++)//X-1（Y）行的合法状态
            {
                if(sta[j]&sta[k]) continue;
                if((sta[j]<<1)&sta[k]) continue;
                if(sta[j]&(sta[k]<<1)) continue;
                for(int c=0;c<=ki;c++)//国王数
                {
                    if(king[j]+c>ki) break;
                    dp[i][j][king[j]+c]+=dp[i-1][k][c];
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++)//因为记录的是前i行,所以加上在前n行的所有合法状态
        ans+=dp[n][i][ki];
    cout<<ans<<endl;
    return 0;
}

码字不易，反正不要钱多少赞一个