Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
正解：状压dp。
状压dp入门题，没什么好讲的吧。。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define ky (1<<n)
#define il inline
#define RG register
#define int long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; int f[][][<<],cnt[<<],n,k,ans; il int gi(){
RG int x=,q=; RG char ch=getchar(); while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar(); while (ch>='' && ch<='') x=x*+ch-,ch=getchar(); return q*x;
} il int calc(RG int x){ RG int ans=; while (x){ ans+=x&,x>>=; } return ans; } il void work(){
n=gi(),k=gi();
for (RG int i=;i<ky;++i){
cnt[i]=calc(i);
if ((i&(i>>)) || (i&(i<<))) continue;
f[][cnt[i]][i]=;
}
for (RG int i=;i<=n;++i)
for (RG int s=;s<ky;++s){
if (s&(s>>) || (s&(s<<))) continue;
for (RG int ss=;ss<ky;++ss){
if (ss&(ss>>) || (ss&(ss<<)) || (s&ss) || (s&(ss>>)) || (s&(ss<<))) continue;
for (RG int p=cnt[ss];p+cnt[s]<=k;++p) f[i][p+cnt[s]][s]+=f[i-][p][ss];
}
}
for (RG int i=;i<ky;++i) ans+=f[n][k][i]; printf("%lld\n",ans); return;
} main(){
File("king");
work();
return ;
}