插头DP：轮廓线动态规划详解
插头DP（轮廓线动态规划）是一种用于解决复杂网格路径与连通性问题的动态规划技巧，尤其擅长处理棋盘覆盖、回路计数等场景。其核心思想是通过逐格转移状态，记录当前处理位置的轮廓线信息，并压缩存储连通性状态。
一、核心概念与原理
1. 轮廓线（轮廓线）
在网格中按行或列逐格推进时，定义一条动态移动的“分界线”，分隔已处理区域和未处理区域。通常采用“行末轮廓线”或“逐格轮廓线”，后者更常见。例如在逐格处理时，轮廓线是当前格子左侧和上方的边线。
2. 插头（Plug）
表示当前格子与相邻格子之间的连接状态。每个格子可能有上下左右四个插头，但实际只需关注轮廓线经过的插头。例如，在逐格处理时，关注左侧和上方的插头。
3. 状态压缩
使用位运算或编码技术将轮廓线上的插头状态压缩为整数。例如，用0/1表示是否存在连接，或用括号序列表示连通块（如广义括号法）。
二、状态设计与转移
以经典的“哈密顿回路计数”问题为例，说明插头DP的典型流程：
1. 状态定义
设当前处理到网格的第i行第j列，状态包括：
– 轮廓线上每个插头的连通情况（如使用括号序列编码）。
– 当前格子的左、上插头状态。
2. 状态转移
分析当前格子可能的连接方式：
– 形成新路径：左、上均无插头，向下或向右创建新插头。
– 合并路径：左、上均有插头，需合并两个连通块并检查是否形成闭环。
– 延续路径：仅有一个插头，延伸路径到下方或右侧。
3. 连通性维护
使用最小表示法或广义括号法管理连通块编号。例如，合并两个插头时，需更新后续插头的连通编号，确保状态一致性。
三、实现技巧与优化
1. 哈希表优化
使用哈希表（如unordered_map）存储状态，避免无效状态的枚举。通常按行滚动更新，减少内存占用。
2. 位运算加速
对插头状态进行位掩码操作。例如，每个插头占用2-3位，多插头状态通过位拼接表示。
3. 剪枝策略
– 提前终止无效状态（如形成多个独立环路）。
– 处理最后一行时，仅保留下方无插头的合法状态。
四、例题解析：HDU 1693 铺砖问题
问题描述：在N×M网格中用L型砖铺满，求方案数。
解法步骤：
1. 状态设计：记录轮廓线上每个位置是否有插头（0/1）。
2. 转移分析：
– 当前格无左、上插头：尝试放置L型砖，生成右、下插头。
– 当前格有左或上插头：延伸插头至右侧或下方。
3. 边界处理：最后一行不能有下插头，最后一列不能有右插头。
代码框架：
cpp
typedef long long ll;
unordered_map
void solve() {
int cur = 0;
dp[cur][0] = 1;
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int nxt = cur ^ 1; dp[nxt].clear(); for (auto &[state, cnt] : dp[cur]) { // 提取左、上插头 int left = (state >> j) & 1;
int up = (state >> (j+1)) & 1;
// 枚举所有转移可能
if (!left && !up) {
// 放置L型砖
dp[nxt][state | (1<