【SCOI2005】互不侵犯

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

说实话，之前就一直想写状压的博客了，奈何一直没有时间搞
互不侵犯应该是最经典的状压题目了

状压的本质就是用一个二进制串表示当前行的状态
所以我们枚举二进制串，判断它是否合法

bool check(int i) {return (!(i&(i<<1)));}

for(register int i=0;i<=maxn;++i)//枚举每一种状态
{
    if(check(i))
    {
        can[++cnt]=i;
        dp[1][cnt][getnum(i)]=1;
    }
}

接着按行枚举，更新它的状态

for(register int i=2;i<=n;++i)//枚举每一行
{
    for(register int j=1;j<=cnt;++j)//枚举每一种状态
    {
        int x=can[j];//上一个状态
        for(register int k=1;k<=cnt;++k)
        {
            int y=can[k];//这一行状态
            if(check(x,y))
            {
                for(register int l=0;l<=m;++l)
                    dp[i][k][getnum(y)+l]+=dp[i-1][j][l];
            }
        }
    }
}

统计答案

for(register int i=1;i<=maxn;++i)
    ans+=dp[n][i][m];

总代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int n,m,cnt,can[(1<<13)];
ll ans=0,dp[15][(1<<13)][90];//第i行，状态的下标为j，k个国王

bool check(int i)
{
    return (!(i&(i<<1)));
}

bool check(int x,int y)
{
    if(x&y) return 0;
    if(x&(y<<1)) return 0;
    if(x&(y>>1)) return 0;
    return 1;
}

int getnum(int sit)
{
    int res=0;
    while(sit)
    {
        res+=sit&1;
        sit>>=1;
    }
    return res;
}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

int main()
{
    read(n);read(m);
    int maxn=(1<<n)-1;
    for(register int i=0;i<=maxn;++i)//枚举每一种状态
    {
        if(check(i))
        {
            can[++cnt]=i;
            dp[1][cnt][getnum(i)]=1;
        }
    }
    for(register int i=2;i<=n;++i)//枚举每一行
    {
        for(register int j=1;j<=cnt;++j)//枚举每一种状态
        {
            int x=can[j];//上一个状态
            for(register int k=1;k<=cnt;++k)
            {
                int y=can[k];//这一行状态
                if(check(x,y))
                {
                    for(register int l=0;l<=m;++l)
                        dp[i][k][getnum(y)+l]+=dp[i-1][j][l];
                }
            }
        }
    }
    for(register int i=1;i<=maxn;++i)
        ans+=dp[n][i][m];
    printf("%lld\n",ans);
}