题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1087

还不错的状态压缩题目，把国王的位置看成1，其余位置看成0，则n行每行的可能出现的状态为1<<n，如果同时考虑n行的状态就为1<<(n*n)，必不可能。

所以先预处理出每行所有的合法状态，及没有相邻的1出现，并处理出每个状态的1的个数。

定义状态dp[i][j][k]表示1-i行中第i行为j状态，1-i行中有k个国王时的方案数。

则转移为dp[i][j][k]=\sum dp[i-1][{j}'][{k}']，{j}'和{k}'为可以转移的合法状态。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll dp[15][1100][110];
 5 ll st[1100], kth[1100];
 6 int main() {
 7     int n, k;
 8     scanf("%d%d", &n, &k);
 9         int len = 0;
10         for (int i = 0; i < (1 << n); i++) {
11             if (!((i << 1)&i)) {
12                 st[++len] = i;
13                 kth[len] = 0;
14                 int w = i;
15                 while (w) {
16                     kth[len] += w % 2;
17                     w /= 2;
18                 }
19             }
20         }
21         for (int i = 1; i <= len; i++) {
22             if (kth[i] <= k)
23                 dp[1][i][kth[i]] = 1;
24         }
25         for (int i = 2; i <= n; i++) {
26             for (int j = 1; j <= len; j++) {
27                 for (int p = 1; p <= len; p++) {
28                     if ((st[j] & st[p]))
29                         continue;
30                     if ((st[j] & (st[p] << 1)))
31                         continue;
32                     if (((st[j] << 1) & st[p]))
33                         continue;
34                     for (int kk = 1; kk <= k; kk++) {
35                         if (kth[j] + kk <= k) {
36                             dp[i][j][kth[j] + kk] += dp[i - 1][p][kk];
37                         }
38                     }
39 
40                 }
41             }
42         }
43         ll ans = 0;
44         for (int i = 1; i <= n; i++) {
45             for (int j = 1; j <= len; j++) {
46                 ans += dp[i][j][k];
47             }
48         }
49         printf("%lld\n", ans);
50         return 0;
51 }