核心逻辑与数学原理
棋盘式状态压缩动态规划（Grid-based State Compression DP）的核心本质是利用空间局部相依性，将高维的二维网格拓扑约束，降维映射为一维行（或列）状态向量之间的状态机交织。
在 17.1 节中，我们探讨了以“顶点集合”为压缩尺度的点集状压。而在处理棋盘格问题（如国王放置、互不侵犯等问题）时，约束条件往往只存在于相邻行与相邻列之间。
1. 空间无后效性的物理隔离
假定一个 $N \times M$ 的网格，我们在放置棋子时，若按照“自上而下，逐行决策”的拓扑序推进，那么当我们在对第 $i$ 行进行棋子放置时：
- 这一行是否合法，仅取决于棋子行内的左右冲突。
- 这一行与历史放置是否冲突，仅取决于它与第 $i-1$ 行的上下及对角线冲突。
- 至于第 $i-2$ 行及更上方的棋子形态，已经被第 $i-1$ 行在空间上物理隔离，对第 $i$ 行没有任何直接的引力作用。
因此，我们不需要记录整个棋盘的宏观面貌，只需要将“当前行”的棋子放置形态压缩为一个二进制掩码 $S$，即可完美满足无后效性。
2. 位运算冲突校验矩阵
假设在一行 $M$ 列的网格中，用二进制状态 $S$ 表示该行棋子的放置情况（1表示放，0表示空）。
-
行内自适应校验：如果两个棋子不能在同方向上相邻（如国王、互不侵犯模型）：
-
左右冲突：若
(S & (S << 1))不为 0，说明存在水平相邻的棋子，该状态直接作废。 -
跨行状态机转移校验：设当前第 $i$ 行状态为 $S$，上一行第 $i-1$ 行状态为 $S_{pre}$：
-
正上下冲突：若
(S & S_pre)不为 0，说明存在垂直相邻的棋子。 -
左下对角线冲突：若
(S & (S_pre << 1))不为 0，说明上一行的某个棋子正对着当前行棋子的左下方。 -
右下对角线冲突：若
(S & (S_pre >> 1))不为 0，说明上一行的某个棋子正对着当前行棋子的右下方。
状态设计与算法推导
以经典的“互不侵犯（King）”问题为例：在 $N \times N$ 的棋盘格中放置 $K$ 个国王，国王能攻击其周围八个方向相邻的格子。求互不侵犯地放置 $K$ 个国王的合法方案总数。
1. 状态空间定义
设状态 $f[i][j][S]$ 表示：已经决策完前 $i$ 行，且整个棋盘上已经放置了 $j$ 个国王，且当前第 $i$ 行的国王放置形态掩码为 $S$ 时的合法方案数。
2. 状态转移方程
对于当前行状态 $S$，首先必须保证其行内合法。接着，我们需要通过 __builtin_popcount(S) 算子获取当前行贡献的国王数量，记为 $c$。
$$\forall S_{pre} \text{ compatible with } S, \quad f[i][j][S] = \sum f[i-1][j - c][S_{pre}]$$
其中“$S_{pre} \text{ compatible with } S$”需严格通过上文所述的三项跨行位运算校验。
C++ 标准源码（NOIP风格）
以下源码为“互不侵犯/国王放置”的工业级标准实现。代码中加入了合法状态空间预处理优化，可大幅榨干常数，确保在 Linux g++ -O2 下实现 0.00s 瞬杀。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 10;
const int MAXK = 100;
long long f[MAXN][MAXK][1 << MAXN];
vector<int> valid_states; // 预处理存储所有行内合法的状态，避免无效枚举
int state_weights[1 << MAXN]; // 预处理每个二进制状态中 1 的个数(即国王数)
int n, k_total;
// 预处理函数：剔除行内本身就左右冲突的状态，并计算权值
void preprocess() {
int max_state = 1 << n;
for (int s = 0; s < max_state; ++s) {
// 水平方向无相邻国王
if (!(s & (s << 1))) {
valid_states.push_back(s);
state_weights[s] = __builtin_popcount(s); // 快速计算二进制中 1 的个数
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> k_total)) return 0;
preprocess();
// 边界初始化：第 0 行没有任何棋子，国王数为 0，形态为 0 的方案数为 1
f[0][0][0] = 1;
// 拓扑轴：逐行推进
for (int i = 1; i <= n; ++i) {
// 枚举当前行状态 S（必须是预处理合法的）
for (int s : valid_states) {
int c = state_weights[s]; // 当前行放置的国王数
// 枚举上一行状态 S_pre（同样来自合法集）
for (int s_pre : valid_states) {
// 跨行冲突全面校验：正上下、左下斜、右下斜
if (s & s_pre) continue;
if (s & (s_pre << 1)) continue;
if (s & (s_pre >> 1)) continue;
// 枚举截止到上一行为止，已经放置的国王总数 j
for (int j = c; j <= k_total; ++j) {
f[i][j][s] += f[i - 1][j - c][s_pre];
}
}
}
}
// 全局收益收集：将最后一行所有可能状态的方案数横向累加
long long ans = 0;
for (int s : valid_states) {
ans += f[n][k_total][s];
}
cout << ans << "\n";
return 0;
}NOIP 实战避坑指南
1. 盲目暴力枚举引发时间复杂度隐式爆炸
- 现象：在棋盘状压中，直接使用普通的循环
for (int s = 0; s < (1<<n); ++s)和for (int s_pre = 0; s_pre < (1<<n); ++s_pre)。若 $N=10$，每行状态数达 $1024$。两层状态循环的计算量就是 $1024 \times 1024 \approx 10^6$，再乘以行数和国王数，直接导致常数爆炸引发运行超时（Time Limit Exceeded）。 - 规避手段：必须进行合法状态预处理。例如当 $N=10$ 时，行内互不相邻的合法状态实际上只有 144 个。将这 144 个状态提取到
std::vector中再跑内部循环，单层循环量从 $1024$ 骤降到 $144$，整体常数被压缩了近 50 倍。
2. 位移边界溢出溢损
- 现象：在判定斜方向冲突时，直接书写
s & (s_pre << 1)。当 $N$ 接近整型边界（或在更宏观的状压中），若位移操作没有做好边界切断，高位溢出的 1 可能会污染前面的内存，或者因为符号位问题产生未定义行为。 - 规避手段：在进行位移校验时，如果担心高位污染，可以通过按位与全集来主动截断：
(s_pre << 1) & ((1 << n) - 1)。
经典 NOIP/洛谷 真题
1. 洛谷 P1896 [SCOI2005] 互不侵犯
- 题意描述：即上文详解的教科书级经典模型。
- 问题本质与解题思路：带有独立计数维度的棋盘状压 DP。通过引入第三维 $j$ 精确卡死国王总数的限制。由于数据范围较小（$N \le 9$），通过一轮状态集预处理和三层循环即可稳稳通过。
2. 洛谷 P2704 [NOI2001] 炮兵阵地
- 题意描述：在一个 $N \times M$ 的有地形限制的棋盘上部署炮兵。炮兵的攻击范围是：上下左右方向各 2 格。也就是说，同一行内任意两个炮兵之间至少要隔 2 格，相邻两行、甚至隔一行的炮兵之间也存在相互冲突。求最多能部署多少个炮兵。$N \le 100, M \le 10$。
- 问题本质与解题思路：跨多阶依赖的棋盘式高维状压 DP。
- 核心难点：炮兵的纵向杀伤力达到了 2 格，这意味着第 $i$ 行的决策不仅受到第 $i-1$ 行的制约，还受到了第 $i-2$ 行的强效制约。传统的二维状态网格无法支撑两代的血统追溯。
- 状态设计：必须扩充状态维度。设 $f[i][S][S_{pre}]$ 表示已经决策完前 $i$ 行，且当前第 $i$ 行的状态为 $S$，上一行第 $i-1$ 行的状态为 $S_{pre}$ 时所能部署的最大炮兵数。
- 状态转移：
$$f[i][S][S_{pre}] = \max \{ f[i-1][S_{pre Visited}][S_{pre\_pre}] \} + \text{count}(S)$$
在校验时，除了执行行内隔 2 格校验 (S & (S << 1)) == 0 && (S & (S << 2)) == 0 外，还要同时满足 (S & S_pre) == 0 以及 (S & S_pre_pre) == 0。通过多加一维状态成功解耦了二阶空间后效性，是棋盘状压的终极进阶必刷题。