核心逻辑与数学原理
插头动态规划（Plug DP），又称轮廓线动态规划（Profile DP），是状态压缩动态规划中最具统治力的终极形态。它专门用于解决棋盘格上的连通性路径闭环问题（例如：在网格中画出一条不自交的闭合回路，或求解哈密顿回路的数量）。
在 17.2 节的棋盘状压中，我们以“整行”为单位进行跨行转移。但如果约束条件变为“路径必须连通且不自交”，仅记录上一行的状态根本无法得知当前的线段在宏观上是如何连接的。如果盲目记录整张图的连通网络，状态量将会发生指数级坍塌。
插头 DP 通过引入轮廓线（Profile）与插头（Plug），将全局的连通性约束完美转化为局部动态机的精确递推。
1. 几何降维：从“行转移”到“逐格轮廓线转移”
插头 DP 不再逐行推进，而是逐格（Cell by Cell）推进。
- 轮廓线（Profile）：分割“已决策格子”和“未决策格子”的折线。对于一个 $M$ 列的棋盘，轮廓线包含 $M$ 条竖直边和 1 条水平边，共 $M+1$ 个部分。
- 插头（Plug）：路径穿过轮廓线的几何具象。由于路径必须连续，每一个格子都有 4 个可能的插头（上、下、左、右）。一个插头存在（记为 1），表示路径从这里穿过轮廓线伸向未决策区域。
2. 连通性的代数解耦：括号表示法（Bracket Notation）
仅仅知道轮廓线上哪些位置有插头（二进制状压）是不够的，因为我们无法判断哪两个插头在内部是相连的。如果不小心将两条原本属于同一个连通块的路径提早闭合，就会在图中间暴毙出一个“局部独立小回路”，导致全局哈密顿回路判定失败。
由于路径在平面网格内互不自交，轮廓线上的插头连通关系具有天然的嵌套性，这在数学上与基态括号匹配完全同构：
- 左括号
(（1 进制/状态 1）：表示这是一个连通块的左端点（插头进）。 - 右括号
)（2 进制/状态 2）：表示这是一个连通块的右端点（插头出）。 - 无插头
_（0 进制/状态 0）：表示当前边上没有路径穿过。
这种基于三种状态（0, 1, 2）的状态压缩，我们通常采用四进制（Bitwise Base-4）进行内存映射。一个拥有 $M$ 列的棋盘，轮廓线上有 $M+1$ 个位置，状态标量通过位运算表示为：State = (p_0 p_1 ... p_{M})_4。
状态设计与算法推导（以哈密顿回路为例）
当我们从左到右、从上到下滚动决策到格点 $(i, j)$ 时，当前格子的左侧轮廓线插头 $L$ 和上方轮廓线插头 $U$ 的状态是已知的。我们需要根据 $L$ 和 $U$ 的括号形态，分类讨论其对右侧和下方新插头的动态转移机（分类讨论矩阵）：
1. 情况 A：$L = 0, U = 0$（无插头流入）
由于是哈密顿回路，每个格子必须被路径流经。当前格子为了活命，必须自己凭空制造一个向右和向下的新路径。
- 转移决策：在新轮廓线上，当前格子的右边和下边分别产生一个
(和)。 - 状态编码：将 $L$ 和 $U$ 的位置改写为 $1$（左括号）和 $2$（右括号）。
2. 情况 B：$L$ 和 $U$ 中有一个为 0，另一个不为 0
说明有一条路径从一侧流入，它在当前格子有两项选择：要么直行，要么拐弯。
- 转移决策：保持原有的括号属性不变，路径可以延续到下方或延续到右方。
- 状态编码：状态保持，位置平移。
3. 情况 C：$L = 1, U = 1$（两个左括号相撞）
两条属于不同连通块的左端点路径在当前格子汇合。它们对接后，这两条路径在全局上连成了一条。
- 拓扑突变：由于两个左括号闭合了，原本与 $U$ 配对的那对括号中的右括号，现在必须被迫降维突变为左括号，以此维持全局括号匹配的平衡性。
4. 情况 D：$L = 2, U = 2$（两个右括号相撞）
与情况 C 对称，两个右括号对接。
- 拓扑突变：原本与 $L$ 对应的那个左括号，必须被迫升维突变为右括号。
5. 情况 E：$L = 2, U = 1$（右括号与左括号相撞）
这代表两条不同的路径片段在中间完美接头。
- 拓扑突变：直接将它们相互抵消，转换为无插头状态 $0$。其余全局括号保持原样。
6. 情况 F：$L = 1, U = 2$（左括号与右括号相撞）
这是最致命的终局判定！左括号在左，右括号在右，说明它们属于同一个连通块的两个端点。如果把它们对接，就会让这个连通块彻底闭合形成回路。
- 回路校验：只有当当前格子恰好是整张棋盘的最后一个合法空格时，这种闭合才是合法的（意味着整张图收尾连成了唯一的大闭合回路）；否则，提早闭合意味着产生了非法局部独立小回路，该状态直接强制剪枝抛弃。
C++ 标准源码（NOIP/省选高精常数通用模板）
由于插头 DP 的有效状态极为稀疏（虽然空间上限是 $4^{M+1}$，但满足括号匹配的合法状态极少），在考场上必须使用哈希表（Hash Table）来动态维护和滚动递推状态空间。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int HASH_SIZE = 4001; // 哈希表容量
const int MAX_STATES = 100005;
int n, m;
int maze[15][15];
int end_x, end_y; // 记录最后一个空格的位置
struct HashTable {
int head[HASH_SIZE], next[MAX_STATES], size;
long long state[MAX_STATES], value[MAX_STATES];
void clear() {
size = 0;
memset(head, -1, sizeof(head));
}
void insert(long long st, long long val) {
int key = st % HASH_SIZE;
for (int i = head[key]; i != -1; i = next[i]) {
if (state[i] == st) {
value[i] += val; // 状态已存在，累加方案数
return;
}
}
// 插入新状态
state[size] = st;
value[size] = val;
next[size] = head[key];
head[key] = size++;
}
} ht[2]; // 滚动哈希表
// 辅助算子：获取四进制状态下第 i 个位置的括号状态
inline int get_bit(long long st, int i) {
return (st >> (i << 1)) & 3;
}
// 辅助算子：设置四进制状态下第 i 个位置的括号状态
inline long long set_bit(long long st, int i, int v) {
return (st & ~(3LL << (i << 1))) | ((long long)v << (i << 1));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> m)) return 0;
end_x = 0; end_y = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char ch; cin >> ch;
if (ch == '.') {
maze[i][j] = 1;
end_x = i; end_y = j; // 动态定位终点
}
}
}
long long ans = 0;
int cur = 0;
ht[cur].clear();
ht[cur].insert(0, 1); // 初始无插头，方案数为 1
for (int i = 1; i <= n; ++i) {
// 致命考场细节：换行时，轮廓线整体需要向右平移一格
// 在四进制下等价于将所有状态统一左移 2 位（即在最左边补一个无插头状态 0）
for (int k = 0; k < ht[cur].size; ++k) {
ht[cur].state[k] <<= 2;
}
for (int j = 1; j <= m; ++j) {
int nxt = cur ^ 1;
ht[nxt].clear();
for (int k = 0; k < ht[cur].size; ++k) {
long long st = ht[cur].state[k];
long long val = ht[cur].value[k];
int p_left = get_bit(st, j - 1); // 左插头 L
int p_up = get_bit(st, j); // 上插头 U
if (!maze[i][j]) {
// 如果是障碍物格子，不能有任何插头流入或流出
if (p_left == 0 && p_up == 0) {
ht[nxt].insert(st, val);
}
continue;
}
// 分类讨论状态机矩阵
if (p_left == 0 && p_up == 0) {
// 情况 A：添加一对新括号
if (maze[i][j + 1] && maze[i + 1][j]) {
long long new_st = set_bit(st, j - 1, 1);
new_st = set_bit(new_st, j, 2);
ht[nxt].insert(new_st, val);
}
}
else if (p_left == 0 || p_up == 0) {
// 情况 B：单插头延续
int p_val = p_left ? p_left : p_up;
if (maze[i][j + 1]) { // 向右延伸
long long new_st = set_bit(st, j - 1, 0);
new_st = set_bit(new_st, j, p_val);
ht[nxt].insert(new_st, val);
}
if (maze[i + 1][j]) { // 向下延伸
long long new_st = set_bit(st, j - 1, p_val);
new_st = set_bit(new_st, j, 0);
ht[nxt].insert(new_st, val);
}
}
else if (p_left == 1 && p_up == 1) {
// 情况 C：两个左括号相撞，改右括号为左
int count = 1;
for (int l = j + 1; l <= m; ++l) {
if (get_bit(st, l) == 1) count++;
if (get_bit(st, l) == 2) count--;
if (count == 0) {
long long new_st = set_bit(st, l, 1);
new_st = set_bit(new_st, j - 1, 0);
new_st = set_bit(new_st, j, 0);
ht[nxt].insert(new_st, val);
break;
}
}
}
else if (p_left == 2 && p_up == 2) {
// 情况 D：两个右括号相撞，改左括号为右
int count = 1;
for (int l = j - 2; l >= 0; --l) {
if (get_bit(st, l) == 2) count++;
if (get_bit(st, l) == 1) count--;
if (count == 0) {
long long new_st = set_bit(st, l, 2);
new_st = set_bit(new_st, j - 1, 0);
new_st = set_bit(new_st, j, 0);
ht[nxt].insert(new_st, val);
break;
}
}
}
else if (p_left == 2 && p_up == 1) {
// 情况 E：右左对接，自然消亡
long long new_st = set_bit(st, j - 1, 0);
new_st = set_bit(new_st, j, 0);
ht[nxt].insert(new_st, val);
}
else if (p_left == 1 && p_up == 2) {
// 情况 F：终局回路闭合
if (i == end_x && j == end_y) {
// 校验剩余插头全为 0 确保其为唯一大回路
long long new_st = set_bit(st, j - 1, 0);
new_st = set_bit(new_st, j, 0);
if (new_st == 0) ans += val;
}
}
}
cur = nxt;
}
}
cout << ans << "\n";
return 0;
}NOIP/省选 实战避坑指南
1. 行末未执行换行状态移位（Shift Operational Bug）
- 现象：当一行决策结束、准备进入下一行的第一个格子时，如果不进行移位操作，上一行最右侧的竖直插头会直接错位变成下一行最左侧的左插头。这在几何上相当于路径直接穿透了棋盘的物理外边界，导致答案恒为 0 或输出大范围脏数据。
- 规避手段：牢记换行控制线：在行循环的最外层、进入列循环之前，必须将当前哈希表中的所有状态标量强制整体左移 2 位（
st <<= 2）。
2. 位运算高位未加 LL 后缀导致截断
- 现象：在通过
set_bit刷新四进制状态时，使用了3 << (i << 1)。如果棋盘列数 $M = 12$，i << 1达到了 $24$，移位操作在默认int（32位）下虽然没有溢出，但如果 $M$ 稍大或涉及更长的轮廓线时，直接引发 32 位整型高位截断，导致状态大面积崩塌。 - 规避手段：涉及高位状压的移位掩码，一律强制追加大整数后缀：
3LL << (i << 1)或(long long)v << (i << 1)。
经典省选/NOI 真题
1. 洛谷 P2289 [HNOI2004] 邮递员
- 题意描述：给定一个 $N \times M$ 的网格，求经过网格中所有顶点恰好一次的闭合回路（哈密顿回路）的总方案数。$N \le 20, M \le 10$。
- 问题本质与解题思路：经典的非障碍物完整哈密顿回路问题。直接套用上文的插头 DP 括号表示法模板。由于此题最终方案数极大，会突破
long long的上限，考场上需要额外外接一个高精度大整数类（__int128或手动高精数组）来替换哈希表中的value存储，即可直接 AC 斩获满分。
2. 洛谷 P3190 [HNOI2007] 神奇游乐园
- 题意描述：给定一个 $N \times M$ 的网格，每个格子里都有一个权值（可正可负）。要求在网格中画出一个合法的单回路（不需要经过所有格子），使得回路所包含的格子权值之和最大。$N \le 100, M \le 6$。
- 问题本质与解题思路：最大权值单回路插头 DP。
- 核心难点：不需要流经所有格子。这意味着每个格子除了被迫生出插头外，还可以选择“完全不画入路径”。
- 状态修正：哈希表中的
value不再存放方案数，而是存放最大权值和。在分类讨论中，增加一个“跳过当前格子”的分支：当 $L=0, U=0$ 时，不仅可以产生新括号，还可以选择保持 $L=0, U=0$ 直接转移到下一格，且不累加当前格子的权值。最终的答案在所有触发情况 F（回路提早闭合）的合法时刻进行全局取 $ ext{max}$ 搜寻。