题目大意
在 \(N \times N\) 的棋盘上放置 \(K\) 个国王，使得它们互不攻击，国王的攻击范围是九宫格的另外八个格子，计算有多少种合法的放置方案。
数据范围：\(1 \le N \le 9\)，\(0 \le K \le N \times N\)
分析
- \(N\) 较小，尝试暴力搜索，时间复杂度为 \(2^{N^2}\)，对于 \(N=9\)（操作数约 \(2e24\)）是不可接受的，剪枝也不太可能，只能另辟蹊径。
- 由于国王的攻击范围很小，只对本行和上下两行有直接影响，考虑从上到下一行一行地放置国王，这样就只受到本行和上面一行已放置国王的约束了。
- 每一行的每个格子只有放或者不放国王两种状态，而 \(N\) 又很小，可以用一个二进制整数来表示每行的状态，考虑状态压缩动态规划。
Solution
标签：状压DP
1. 状态定义
定义 \(dp[S][k][i]\) 表示：
- 当前处理到第 \(i\) 行；
- 第 \(i\) 行的状态为 \(S\)（如果第 \(j\) 列放置了国王，则第 \(j\) 位为 \(1\)，否则为 \(0\)）；
- 已经放置了 \(k\) 个国王；
- 值为满足这些条件的方案总数。
2. 状态转移
1. 行内约束：同一行内，国王不能相邻（包括左右相邻）
- 即状态 \(S\) 不能有相邻的 \(1\) ：(\(S\) & (\(S\) >> \(1\))) \(==\) \(0\)
2. 行间约束：相邻两行的国王不能相互攻击
- 上下攻击：(\(S\) & \(L\)) \(==\) \(0\)
- 左上/右上攻击：(\(S\) & (\(L\) >> \(1\))) \(==\) \(0\) 和 (\(S\) & (\(L\) << \(1\))) \(==\) \(0\)
- 可以合并为：(\(S\) & \(L\)) \(==\) \(0\) && (\(S\) & (\(L\) >> \(1\))) \(==\) \(0\) && (\(S\) & (\(L\) << \(1\))) \(==\) \(0\)
3. 国王数量约束：
- 总国王数不能超过 \(K\)
状态转移方程
\[dp[S][t_1 + t_2][i] = dp[S][t_1 + t_2][i] + dp[L][t_1][i - 1]
\]
- \(S\)（当前行状态）
- \(L\)（上一行状态）
- \(t_1\)（已放置国王数）
- \(t_2\)（当前行国王数）
时间复杂度
- 总时间复杂度：\(O(N \times 2^{2N} \times N^2)\)
代入 \(N=9\)：
理论计算量：\(9 \times 262,144 \times 81 ≈ 191,102,976\) 次操作（约 \(1.9 \times 10^8\)），搭配剪枝操作，实际操作数更小，可以接受。
参考代码
#include<bits/stdc++.h>
using namespace std;// dp[S][k][i] 表示第i行状态为S，总共放了k个国王的总方案数
long long dp[1<<9][82][10];
long long n, mk, ans; // mk为国王总数K// 计算二进制中1的个数（即当前状态放置的国王数）
long long popcount(int x) {long long sum = 0;while(x) {if(x & 1) sum++;x >>= 1;}return sum;
}int main() {cin >> n >> mk;// 初始化第一行for(int S = 0; S < (1 << n); S++) {// 检查行内是否合法：没有相邻的国王if(!(S & (S >> 1))) {dp[S][popcount(S)][1] = 1;}}// 状态转移：从第2行到第n行for(int i = 2; i <= n; i++) {// 枚举上一行状态Lfor(int L = 0; L < (1 << n); L++) {// 剪枝：上一行状态必须合法if(L & (L >> 1)) continue;// 枚举当前行状态Sfor(int S = 0; S < (1 << n); S++) {// 检查行内是否合法if(S & (S >> 1)) continue;// 检查行间是否合法if((S & L) || (S & (L >> 1)) || (S & (L << 1))) continue;// 当前行放置的国王数int t2 = popcount(S);// 枚举之前已放置的国王数for(int t1 = 0; t1 + t2 <= mk; t1++) {dp[S][t1 + t2][i] += dp[L][t1][i - 1];}}}}// 统计答案：第n行所有状态中，国王数为mk的方案数之和for(int S = 0; S < (1 << n); S++) {ans += dp[S][mk][n];}cout << ans;return 0;
}