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