Bzoj1087 [scoi2005]互不侵犯king

Posted by yjjr's blog on February 6, 2018

标签:状压DP

Description

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

Input

  只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

Output

  方案数。

Sample Input

3 2

Sample Output

16

 

分析:设f[i][j][x]表示前i行放置了j的国王,且当前行状态(用二进制表示)为x时的方案数

判断状态是否符合要求可以枚举上一行状态,进行判断:如果当前行状态x和上一行状态y,符合下列任意条件,那么就是不符合要求的

X&(y<<1)

(x<<1)&y

X&y

预处理Num[x],为状态为x时,该行放置国王的数量

 

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
    LL f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxm=1006;
LL n,k,ans=0,f[16][maxm][maxm],num[maxm];
bool flag[maxm];
int main()
{
    n=read(),k=read();
    rep(i,0,(1<<n)-1)
        if(!(i&(i<<1))){
            flag[i]=true;
            int t=i;
            while(t){
                num[i]+=(t&1);
                t>>=1;
            }
            f[1][num[i]][i]=1;
        }
    rep(i,2,n)
        rep(j,0,k)
            rep(x,0,(1<<n)-1){
                if(!flag[x])continue;
                if(num[x]>j)continue;
                rep(y,0,(1<<n)-1){
                    if(!flag[y])continue;
                    if(x&y||x&(y<<1)||(x<<1)&y)continue;
                    f[i][j][x]+=f[i-1][j-num[x]][y];
                }
            }
    rep(i,0,(1<<n)-1)ans+=f[n][k][i];
    cout<<ans<<endl;
    return 0;
}   




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr