状压DP
我写的太水了……64ms才过，估计还有更好的做法，希望各位神犇不吝赐教>_<。
嗯这题很明显每一行都可以用一个2进制数表示放置方式的，（1表示放，0表示不放）。然后预处理一下所有合法状态（同一行内的国王之间不会互相攻击），然后记f[i][j][k]为第i行，用第j种合法放置方式放国王，总共放了k个国王的方案数，转移的时候枚举上一行的状态，看是否和这一行的冲突（和预处理一样可以用位运算加速），然后累加即可，很基础的状压DP。
WA了一次的原因：最后答案可能会爆int，必须用longlong（或者unsigned int也行吧？）
/**************************************************************
Problem: 1087
User: ProgrammingApe
Language: C++
Result: Accepted
Time:64 ms
Memory:8480 kb
****************************************************************/ //BZOJ 1087
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int n,K,num[],a[],cnt;
long long f[][][]; int count(int x){
int ans=;
while(x){ans+=x&; x>>=;}
return ans;
} int main(){
// freopen("file.in","r",stdin);
scanf("%d%d",&n,&K);
F(i,,(<<n)-){
int s=count(i);
if ((s>K) || (i&(i>>)) || (i&(i<<))) continue;
a[++cnt]=i;
num[cnt]=s;
}
F(j,,cnt)
f[][j][num[j]]=;
F(i,,n)
F(j,,cnt)
F(m,,n*n)
F(k,,cnt){
if (f[i-][j][m]==) continue;
if ( (a[j]&a[k]) || (a[j]&(a[k]>>)) || (a[j]&(a[k]<<)) || m+num[k]>K) continue;
f[i][k][num[k]+m]+=f[i-][j][m];
}
long long ans=;
F(j,,cnt) ans+=f[n][j][K];
printf("%lld\n",ans);
return ;
}