首先呢，这题基本学过状压DP的都会做了...
那么我来讲一下该怎么使用状压DP，如果要运用状压DP，那么得先熟悉位运算，具体就请问度娘祖宗三十二代，嗯。那么状压DP主要运用于在某些问题上如果是普通DP，那么无法表示出题目所需要的状态，比如这一题，如果是普通的DP，那么表示不出来棋盘的状态，那么只能打空炮。
但是换个角度想，实际上我们放棋子，我们可以想，如果一个位置上没有棋子就是0，不然就是1，那么就可以表示出来棋盘的状态了，那么类似1010101的这种状态你想到了什么，没错二进制，状压DP就是将DP的状态压成一个二进制数，但实际上它还是一个十进制数，只不过在判断状态是否合法的时候用到位运算将它转换成二进制进行运算，在这题中，我们就有了办法表示出任意行的状态，但是题目中的要求还涉及到上一行的状态，我们就可以想到我们设DP[N][K(表示现在放的国王个数)][1<<N-1(二进制下表示状态，1<<n这些自行百度位运算)]，那么状态转移方程就是DP[i][k][S]+=DP[i-1][k'(上一行放得国王的个数)][S']，那么就可以看出来，在枚举状态的时候，枚举当前这一行的状态以及上一行的状态(之前做一个预处理，将左右相邻的状态排除掉)，然后判断这一行与上一行的状态是否合法(X&Y,X&Y<<1,X&Y>>1)，然后状态转移，在转移方程中还有个不确定的因素就是国王的个数，国王的个数取决于当前的状态里1的个数，于是我们可以预处理出每一个当前行中合法的状态中的1的个数，方程就转变为DP[i][K][S]+=DP[i-1][k(枚举已经放的国王的个数)-num[S]][S'],那么至此，所有问题迎刃而解了，那么附上正解代码：(实际上可以优化:增加数组记录合法状态，到时候枚举数组长度，取出数组保存的状态，就行)
这里因为空间问题，所以采用滚动数组优化

include<bits/stdc++.h>

using namespace std;
int n, k,num[1<<9+5],t,now,i,j,nex;
long long f[2][9*9+5][1<<9+5];
bool flag[1<<9+5];
long long ans,sum;
void init()
{
for (int i=0;i<(1<<n);i++)
if (!(i&(i<<1)))
{
flag[i]=true;
t=i;
while (t)
{
num[i]+=(t&1);
t>>=1;
}
f[1][num[i]][i]=1;
}
}

int main()
{
scanf("%d%d",&n,&k);
init();
for (i=2;i<=n;i++)
for (j=0;j<=k;j++)
for (now=0;now<(1<<n);now++)
{
if (!flag[now])
continue;
if (num[now]>j)
continue;
for (nex=0;nex<(1<<n);nex++)
{
if (!flag[nex])
continue;
if ((nex&now)||((now<<1)&nex)||((now>>1)&nex))
continue;
sum+=f[(i-1)%2][j-num[now]][nex];
f[i%2][j][now]=sum;
}
sum=0;
}
for (int i=0;i<(1<<n);i++)
ans+=f[n%2][k][i];
printf("%lld",ans);
return 0;
}