标签:状压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;
}
