题目链接
状压操作感觉挺复杂的。
解题思路
首先，这样一个矩阵，仅仅有两个状态，放与不放。嗯。我们考虑DP或搜索。
很明显，搜索非常优（la）秀（ji）。我们需要用DP。
由于N很小，我们选择状态压缩。每一行中，国王放的情况是一定的，所以情况以及其对应个数我们可以直接预处理出来，然而同时每一行中的国王必须要隔开，对的，不能够互相攻击，我们要进行判断。
国王是限制条件，我们要放到DP中，然后有了行的状态，我们枚举行，放到dp中。
综上所述
dp[i][j][k]表示前i行，j号状态所要放的国王数k
那么肯定是由i-1行中一个满足条件的dp转移过来，于是。
dp[i][j][s]=sum(dp[i-1][k][s-gs[j]])。
判断就非常简单明了，我们用&（都1为1，否则为0）
两个状态，如果（zhuangtai(j) & zhuangtai(p)）那肯定不行。
然后就是斜着来。左移就差不多了
然后照着来，最后找出答案，提一点，由于题目仅仅控制国王数一定，我们就要枚举两个变量。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,k;
long long state[100005],king[100005],dp[15][10005][105],tot;
long long ans;
void find(){
int m = (1 << n) - 1;
for (int i = 0;i <= m;i ++){
if (!((i << 1)&i)){
state[++ tot] = i;
int t = i;
while (t){
king[tot] += t % 2;
t /= 2;
}
}
}
}
int main(){
scanf ("%d%d",&n,&k);
find();
for (int i = 1;i <= tot;i ++)
if (king[i] <= k)
dp[1][i][king[i]] = 1;
for (int i = 2;i <= n;i ++){
for (int j = 1;j <= tot;j ++){
for (int p = 1;p <= tot;p ++){
if (state[j] & state[p])
continue;
if ((state[j] << 1) & state[p])
continue;
if ((state[p] << 1) & state[j])
continue;
for(int z = 1;z <= k;z ++){
if (king[j] + z <= k)
dp[i][j][king[j] + z] += dp[i - 1][p][z];
}
}
}
}
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= tot;j ++)
ans += dp[i][j][k];
printf("%lld",ans);
}