# 「SCOI2005」互不侵犯 题解

题目解析

这是一个经典的棋盘放置问题，要求在 $N \times N$ 的棋盘上放置 $K$ 个国王，使得任意两个国王都不能相互攻击。国王的攻击范围是其周围8个相邻的格子（上下左右及四个对角线方向）。

算法思路

状态压缩动态规划

由于 $N \leq 9$，可以使用状态压缩动态规划来解决：

1.状态表示：

a.使用二进制数表示每一行的国王放置情况

b.表示该位置放置国王，0 表示不放置

2.合法状态预处理：

a.同一行内，国王不能相邻（包括对角线相邻）

b.通过DFS生成所有可能的合法行状态

3.状态转移：

a.使用三维DP数组 dp[i][j][k]，其中：

i 表示当前处理的行数

j 表示当前行的状态编号

k 表示已经使用的国王总数

b.值表示对应的方案数

4.兼容性检查：

a.相邻两行的状态必须满足：

b.同一列不能同时有国王

c.相邻列不能同时有国王（防止对角线攻击）

解题过程

步骤1：预处理合法状态 使用DFS生成所有合法的单行状态

记录每个状态对应的二进制表示和国王数量

排除同一行内国王相邻的情况

步骤2：初始化第一行 对于每个合法状态，设置对应的DP值

dp[1][j][sta[j]] = 1，其中 sta[j] 是该状态的国王数

步骤3：状态转移 对于第 i 行（i ≥ 2）：

遍历所有可能的当前行状态 j

遍历所有可能的前一行状态 x

检查状态 j 和 x 是否兼容：

垂直方向不能有冲突

对角线方向不能有冲突

如果兼容，则更新DP值：

text dp[i][j][l] += dp[i-1][x][l - sta[j]] 其中 l 是当前总国王数

步骤4：统计结果 累加最后一行所有状态中国王数恰好为 $K$ 的方案数

输出最终结果

** 算法特点**

1.时间复杂度：$O(N \times S^2 \times K)$，其中 $S$ 是合法状态数

2.空间复杂度：$O(N \times S \times K)$

3.优化点：通过状态压缩和兼容性剪枝，大幅减少搜索空间

这种方法高效地解决了棋盘放置问题，避免了暴力搜索的指数级复杂度。