Core Logic and Mathematical Principles
Plug Dynamic Programming (Plug DP), also known as Profile Dynamic Programming, is the most dominant and ultimate form of state compression dynamic programming. It is specifically designed to solve the connectivity path loop problem on grids (for example, drawing a non-self-intersecting closed loop on the grid, or counting the number of Hamiltonian cycles).
In Section 17.2's grid compression, we performed inter-row transfers on a "whole row" basis. However, if the constraint changes to "the path must be connected and non-self-intersecting," merely recording the state of the previous row cannot reveal how the current segments are connected on a macro level. Blindly recording the connectivity network of the entire graph will lead to an exponential collapse of the state quantity.
Plug DP introduces Profiles and Plugs, perfectly transforming the global connectivity constraints into precise recursions of local dynamic programming.
1. Geometric Dimensionality Reduction: From "Row Transfer" to "Cell-by-Cell Profile Transfer"
Plug DP no longer advances row by row but cell by cell (Cell by Cell).
- Profile: A polyline that separates the "decided cells" from the "undecided cells." For a grid with $M$ columns, the profile contains $M$ vertical edges and 1 horizontal edge, totaling $M+1$ parts.
- Plug: A geometric representation of the path crossing the profile. Since the path must be continuous, each cell has 4 possible plugs (up, down, left, right). The existence of a plug (denoted as 1) indicates that the path crosses the profile and extends into the undecided area.
2. Algebraic Decoupling of Connectivity: Bracket Notation
Knowing only the positions of plugs on the profile (binary compression) is insufficient, as we cannot determine which two plugs are internally connected. If we accidentally close two paths that originally belong to the same connected component too early, it will create a "locally independent small loop" in the middle of the graph, leading to a failure in determining the global Hamiltonian cycle.
Since the paths do not intersect in the planar grid, the connectivity relationships of the plugs on the profile have a natural nesting property, which is mathematically isomorphic to ground state bracket matching:
- Left bracket
((base-1/state 1): Indicates that this is the left endpoint of a connected component (plug in). - Right bracket
)(base-2/state 2): Indicates that this is the right endpoint of a connected component (plug out). - No plug
_(base-0/state 0): Indicates that no path crosses the current edge.
This state compression based on three states (0, 1, 2) is usually mapped in memory using base-4 (Bitwise Base-4). A grid with $M$ columns has $M+1$ positions on the profile, and the state scalar is represented using bitwise operations as: State = (p_0 p_1 ... p_{M})_4.
State Design and Algorithm Derivation (Taking Hamiltonian Cycle as an Example)
As we roll from left to right and top to bottom to decide on the grid point $(i, j)$, the states of the left profile plug $L$ and upper profile plug $U$ are known. We need to classify the discussion of their bracket forms to determine the dynamic transfer mechanism for the new plugs on the right and below (classification discussion matrix):
1. Case A: $L = 0, U = 0$ (No plugs flowing in)
Since this is a Hamiltonian cycle, every cell must be traversed by the path. To survive, the current cell must create a new path extending right and down from nothing.
- Transfer Decision: In the new profile, the right and bottom sides of the current cell produce a
(and)respectively. - State Encoding: Rewrite the positions of $L$ and $U$ as $1$ (left bracket) and $2$ (right bracket).
2. Case B: One of $L$ and $U$ is 0, the other is not
This indicates that a path is flowing in from one side, giving the current cell two choices: either continue straight or turn.
- Transfer Decision: Retain the original bracket properties; the path can extend downwards or to the right.
- State Encoding: Keep the state and shift the position.
3. Case C: $L = 1, U = 1$ (Two left brackets collide)
Two left endpoints of different connected components converge at the current cell. After connecting, these two paths globally form one.
- Topological Mutation: Since the two left brackets close, the corresponding right bracket in the pair that was originally paired with $U$ must be forced to mutate into a left bracket to maintain the balance of global bracket matching.
4. Case D: $L = 2, U = 2$ (Two right brackets collide)
Symmetrically to Case C, two right brackets connect.
- Topological Mutation: The corresponding left bracket that originally paired with $L$ must be forced to mutate into a right bracket.
5. Case E: $L = 2, U = 1$ (Right bracket collides with left bracket)
This indicates that two different path segments perfectly connect in the middle.
- Topological Mutation: Directly cancel them out, converting them into the no plug state $0$. The remaining global brackets remain unchanged.
6. Case F: $L = 1, U = 2$ (Left bracket collides with right bracket)
This is the most critical endgame determination! The left bracket is on the left and the right bracket is on the right, indicating that they are the two endpoints of the same connected component. If they connect, it will completely close the connected component into a loop.
- Loop Verification: This closure is only valid if the current cell is exactly the last legal empty cell of the entire grid (indicating that the entire graph has been closed into a unique large loop); otherwise, premature closure means producing an illegal local independent small loop, and this state is directly pruned and discarded.
C++ Standard Source Code (NOIP/Provincial Selection High Precision Constant General Template)
Due to the extremely sparse valid states of Plug DP (although the upper limit is $4^{M+1}$, the legal states that satisfy bracket matching are extremely few), during the exam, it is essential to use a hash table to dynamically maintain and roll forward the state space.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int HASH_SIZE = 4001; // Hash table capacity
const int MAX_STATES = 100005;
int n, m;
int maze[15][15];
int end_x, end_y; // Record the position of the last empty cell
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; // State already exists, accumulate the number of schemes
return;
}
}
// Insert new state
state[size] = st;
value[size] = val;
next[size] = head[key];
head[key] = size++;
}
} ht[2]; // Rolling hash table
// Helper Operator: Get the bracket state of the i-th position in base-4 state
inline int get_bit(long long st, int i) {
return (st >> (i << 1)) & 3;
}
// Helper Operator: Set the bracket state of the i-th position in base-4 state
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; // Dynamically locate the endpoint
}
}
}
long long ans = 0;
int cur = 0;
ht[cur].clear();
ht[cur].insert(0, 1); // Initial no plugs, number of schemes is 1
for (int i = 1; i <= n; ++i) {
// Critical exam detail: When switching lines, the profile must shift right by one cell
// In base-4, this is equivalent to shifting all states left by 2 bits (i.e., adding a no plug state 0 on the leftmost side)
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); // Left plug L
int p_up = get_bit(st, j); // Upper plug U
if (!maze[i][j]) {
// If it is an obstacle cell, no plugs can flow in or out
if (p_left == 0 && p_up == 0) {
ht[nxt].insert(st, val);
}
continue;
}
// Classify discussion of state machine matrix
if (p_left == 0 && p_up == 0) {
// Case A: Add a new pair of brackets
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) {
// Case B: Single plug continuation
int p_val = p_left ? p_left : p_up;
if (maze[i][j + 1]) { // Extend right
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]) { // Extend down
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) {
// Case C: Two left brackets collide, change right bracket to left
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) {
// Case D: Two right brackets collide, change left bracket to right
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) {
// Case E: Right and left connect, naturally cancel out
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) {
// Case F: Endgame loop closure
if (i == end_x && j == end_y) {
// Verify that the remaining plugs are all 0 to ensure it is a unique large loop
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（回路提早闭合）的合法时刻进行全局取 $\text{max}$ 搜寻。