一、题目理解
国王可以向附近的八个方向进行攻击，所以穷举一下十六种可能，与测试用例对上了。
二、题目解析
题目很明确，一个国王只能攻击它相邻的\(8\)个格子（\(8\)联通）
那么如果再次简化，可以发现其实是\(6\)联通
即：只要保证每一个国王的左上、上、右上、左、右都没有其他的国王就行了
那么再简化一步说明，每一行的状态只与上一行的状态有关
显然这符合\(dp\)的原则：无后效性
那么这时对于这些合法的可能状态有：
\(f[i][x][t+Count(x)]=∑f[i-1][y][t]\)
其中\(t\)为前面放的国王总数，\(Count(i)\)表示状态\(i\)在二进制下的\(1\)的个数
那么目标状态即为\(∑f[n][x][K]\)
还是挺好理解的对吧~
为了优化常数，我们可以先预处理出一些合法的状态，存在一个数组里
状态表示
\(f[i][j][k]\) 表示前\(i\)行已经摆完，放入了\(j\)个国王，并且第\(i\)行状态是\(k\)的所有方案的集合。
属性
\(count\)
状态计算
本行的预放入状态，需要与上一行兼容，并且本行预放入的状态中包含的国王个数，需要小于限定的国王个数。
在满足了上面的两个条件后，我们就可以通过上一行和本行的状态，计算出由上一行迁移过来的方案数量。
约束就是同行不能有国王左右相邻，并且相邻两行不能有国王上下相邻,\(45\)度相邻！
- 某一个状态是否合法【同行左右相邻检查】
就是检查是不是二进制数中存在连续的数字\(1\)。
//判断一行是不是有连续1
bool check(int x) {
return !(x & x >> 1);
}
上面的状态是否合法是后面的基石，必须在上面成立的条件下进行讨论后面的情况：
双重循环遍历所有可行的状态，尝试找出状态之间的兼容关系，并记录到数组中，防止重复计算。
//i与i-1行之间的兼容关系记录下来
for (int a: st)
for (int b: st) {
//a&b==0:同列不是同时为1，表示列上面国王不冲突
//check(a|b)： 经或处理后的数字，如果存在连续的1，就表示斜45度有国王，不合法,妙不可言
if ((a & b) == 0 && check(a | b))
head[a].push_back(b);//记录合法的状态转移关系
}
-
相邻行上下相邻检查
这个检查很有技巧，方法是判断\(a \& b ==0\)。如果\(a,b\)存在某一位上的数字都是\(1\)，则必然\(a \& b>0\),要想等于\(0\)，必须保证没有任何一个位置同时都是\(1\)，即相邻行之间不冲突。 -
相邻行45度相邻检查
这个检查就更有意思，采用了\(a|b\)之后的结果再去用\(check\)检查的办法，如果存在连续的\(1\)，就表示\(45\)度相关。
//i与i-1行之间的兼容关系记录下来
for (int a: st)
for (int b: st) {
//a&b==0:同列不是同时为1，表示列上面国王不冲突
//check(a|b)： 经或处理后的数字，如果存在连续的1，就表示斜45度有国王，不合法,妙不可言
if ((a & b) == 0 && check(a | b))
head[a].push_back(b);//记录合法的状态转移关系
}
三、朴素版本代码
#include <bits/stdc++.h>
using namespace std;
//棋盘式状态压缩DP
typedef long long LL;
const int N = 11; //棋盘的长宽上限
const int M = 1 << 10; //二进制枚举的状态数量上限，因为n最大是10,就是2^10个状态
const int K = 110; //国王的个数上限
int n; //n*n的棋盘
int m; //国王的数量
vector<int> st; //所有合法的状态（预处理的结果）
vector<int> head[M]; //某个状态兼容哪些状态（预处理的结果）
int cnt[M]; //记录每种状态中的数字1个数，了解本行使用了多少个国王
//完成前i行，使用了j个国王，现在的状态是k:001010111之类，存在的是二进制对应的十进制数
LL f[N][K][M];
//判断一行是不是有连续1
bool check(int x) {
return !(x & x >> 1);
}
//统计某个状态中数字1的数量
int count(int x) {
int res = 0;
for (int i = 0; i < n; i++) res += x >> i & 1;
return res;
}
int main() {
cin >> n >> m;
//1、可行的合法状态预处理
for (int i = 0; i < 1 << n; i++)
if (check(i)) st.push_back(i), cnt[i] = count(i);
//i与i-1行之间的兼容关系记录下来
for (int a: st)
for (int b: st) {
//a&b==0:同列不是同时为1，表示列上面国王不冲突
//check(a|b)： 经或处理后的数字，如果存在连续的1，就表示斜45度有国王，不合法,妙不可言
if ((a & b) == 0 && check(a | b))
head[a].push_back(b);//记录合法的状态转移关系
}
//2、DP
//已经摆完了前0行，放置了0个国王，当前状态全是0，这种情况下只有全是0的状态是合法的，方案数为0.
f[0][0][0] = 1;
for (int i = 1; i <= n; i++) //枚举每一行
for (int j = 0; j <= m; j++) //枚举国王个数
for (int a: st) { //枚举第i行的每一种可能状态
for (int b: head[a]) { //s状态与哪些状态兼容
int c = cnt[a]; //状态st[s]的国王数量也可以一并预处理出来，当然也可以现用现算
//上面的j循环，限定了国王的数量上限
if (j >= c) f[i][j][a] += f[i - 1][j - c][b];//从上一层的状态转化而来
}
}
//结果
LL ans = 0;
//在填充完n行之后，将m个国王放完，每一个合法状态都是可能的解，需要累加起来才是答案
for (int a: st) ans += f[n][m][a];
printf("%lld", ans);
return 0;
}
四、滚动数组优化版本代码
#include <bits/stdc++.h>
using namespace std;
//棋盘式状态压缩DP
typedef long long LL;
const int N = 11; //棋盘的长宽上限
const int M = 1 << 10; //二进制枚举的状态数量上限，因为n最大是10,就是2^10个状态
const int K = 110; //国王的个数上限
int n; //n*n的棋盘
int m; //国王的数量
vector<int> st; //所有合法的状态（预处理的结果）
vector<int> head[M]; //某个状态兼容哪些状态（预处理的结果）
int cnt[M]; //记录每种状态中的数字1个数，了解本行使用了多少个国王
//第一维：完成前i行，第二维：使用了j个国王，第三维：现在的状态是x:001010111之类，存在的是二进制对应的十进制数
LL f[2][K][M];
//判断一行是不是有连续1
bool check(int x) {
return !(x & x >> 1);
}
//统计某个状态中数字1的数量
int count(int x) {
int res = 0;
for (int i = 0; i < n; i++) res += x >> i & 1;
return res;
}
int main() {
cin >> n >> m;
//1、可行的合法状态预处理
for (int i = 0; i < 1 << n; i++)
if (check(i)) st.push_back(i), cnt[i] = count(i);
//i与i-1行之间的兼容关系记录下来
for (int a: st)
for (int b: st) {
//a&b==0:同列不是同时为1，表示列上面国王不冲突
//check(a|b)： 经或处理后的数字，如果存在连续的1，就表示斜45度有国王，不合法,妙不可言
if ((a & b) == 0 && check(a | b))
head[a].push_back(b);//记录合法的状态转移关系
}
//2、DP
//已经摆完了前0行，放置了0个国王，当前状态全是0，这种情况下只有全是0的状态是合法的，方案数为0.
f[0][0][0] = 1;
for (int i = 1; i <= n; i++) //枚举每一行
for (int j = 0; j <= m; j++) //枚举国王个数
for (int a: st) { //枚举第i行的每一种可能状态
f[i & 1][j][a] = 0; //清零
for (int b: head[a]) { //s状态与哪些状态兼容
int c = cnt[a]; //状态st[s]的国王数量也可以一并预处理出来，当然也可以现用现算
//上面的j循环，限定了国王的数量上限
if (j >= c) f[i & 1][j][a] += f[i - 1 & 1][j - c][b];//从上一层的状态转化而来
}
}
//结果
LL ans = 0;
//在填充完n行之后，将m个国王放完，每一个合法状态都是可能的解，需要累加起来才是答案
for (int a: st) ans += f[n & 1][m][a];
printf("%lld", ans);
return 0;
}