Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
状压DP入门题
f[i][j][k]表示放完i行，第i行状态为j，i行放了k个
f[i][j][k]表示放完i行，第i行状态为j，i行放了k个
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
LL state[],num[];
LL f[][][];
LL N,K,m;
void Deal()
{
for (LL i=;i<=(<<N)-;++i)
{
LL x=i,pre=-,cnt=;;
for (LL j=;j<=;++j)
{
if (x&==pre) break;
if (x&) cnt++;
pre=x&;
x>>=;
}
if (x== && cnt<=K)
state[++m]=i,num[m]=cnt;
}
} bool check(LL x,LL y)
{
if ((state[x]&state[y])!=) return false;
if (((state[x]<<)&state[y])!=) return false;
if (((state[y]<<)&state[x])!=) return false;
return true;
} int main()
{
scanf("%lld%lld",&N,&K);
Deal();//预处理每一行的可能情况
for (LL i=;i<=m;++i) f[][i][num[i]]=;
for (LL i=;i<=N;++i)
for (LL j=;j<=m;++j)//当前行状态
for (LL k=;k<=m;++k)
for (LL l=num[j];l<=K;++l)
if (check(j,k))
f[i][j][l]+=f[i-][k][l-num[j]];
LL ans=;
for (LL i=;i<=m;++i)
ans+=f[N][i][K];
printf("%lld",ans);
}