出自陈丹琦的《基于连通性状态压缩的动态规划问题》。

论文 PDF

一般基于棋盘（方格表）模型。

【（轮廓线）插头 DP】

如果有简单点的例题就好了，但没有找到，那么直接拿插头 DP 模板题吧。

插头 DP 模板题

给定一个方格表，有一些格子放了障碍物，求用一条回路恰好经过所有格子的方案数。\(n,m\le 12\)。

连模板都是黑色

【插头】

因为要研究格子之间的连通性，而每个格子只会与上下左右四个格子连通，所以可以想象在每个格子里有一个中枢；然后这个中枢有上下左右四个可能的插头。

如果一个格子有对应方向的插头，就表示这个格子要和对应方向的相邻格子连通。

再观察到题目中回路的条件。在一条回路中，每个格子的度恰好为 \(2\)。也就是说，每个格子恰好有两个插头。

【连通性的表示】

对于这种数据范围很小的，我们根据以往的经验，应该会想到状压 DP（事实上插头 DP 也只是对状压的优化）。

如果是常见的状压 DP，只需要用状态记录每一行每个格子是否有向下的插头即可；但是这个问题还要考虑格子之间的连通性，因此还要额外压缩一维状态用来记录连通性。

问题来了：怎么把连通性压缩为一个数？

论文中提到三种表示方法，分别是最小表示法、最左表示法和括号表示法。括号表示法暂且按下不表。

最小表示法和最左表示法，其实都是把同一个连通块的元素赋予同一个编号。

1. 最小表示法：循环 \(i\leftarrow 1\sim n\)，如果 \(i\) 有编号，跳过；如果 \(i\) 是障碍物，赋值编号为 \(0\)；否则从 \(i\) 搜索一遍，把所有与它连通的都赋予一个新编号。

2. 最左表示法：如果是障碍物，编号 \(0\)；否则编号为它所在连通块最靠左的格子编号。

因为最小表示法比较好写，比较常用，下面都用最小表示法了。

【尝试状压 DP】

看到棋盘、\(n,m\le 12\)，不由自主想到状压 DP。本来应该是 \(dp[i][S]\)：记录第 \(i\) 行向下连通的状态即可。但是还要额外记录一下连通性，因此状态描述变成 \(dp[i][S_0][S_1]\)：\(S_0\) 表示第 \(i\) 行向下连通状态（其实就是记录有没有向下的插头），\(S_1\) 表示第 \(i\) 行内部的连通状态。

（注意 \(i+1\sim n\) 行的格子显然不可能跨越第 \(i\) 行与 \(1\sim i-1\) 行的格子连通，所以这是无后效性的一个状态定义）

在状态转移的时候，枚举 \(S_0\) 可以衍生出的所有后续状态。

我们发现，如果一个格子没有向下的插头，它与其他格子的连通性是没有记录的意义的：因为和它连通必然用到其他格子。所以只需要记录插头的连通情况即可。

而因为我们只记录有插头的地方，所以可以把 \(S_0,S_1\) 直接合并为 \(S\)（把 "有没有插头" 和 "格子连通性" 合并成 "插头连通性"）。如果这个位置没有插头，对应位上记录 \(0\)，其他地方就用最小表示法。这是一个极大的优化。

【轮廓线/插头 DP】

状压 DP 是一行一行递推的，有没有可能可以按格子递推呢？当然可能。而这就是轮廓线 DP。

轮廓线：把已递推的格子和未递推的格子分开的线。

轮廓线 DP 要求每次可能对下方产生影响的，都是 "边界" 上的格子；而形成回路，显然只有边界上的格子可以连接。注意轮廓线长度为 \(m+1\)，如果刚好是一条直线可以认为最右边有一个不存在的空位置。

省略一些过程，轮廓线 DP 的状态描述为：\(dp[i][j][S]\) 表示递推到格子 \((i,j)\)，此时轮廓线上插头联通状态为 \(S\)。

那我们把普通状压改成轮廓线获得了什么？

首先显而易见的，空间从 \(O(n2^m)\) 变成 \(O(nm2^m)\) 了。空间多了，但是我们换来了时间的大幅减少。

普通状压 DP 需要从一个状态 \(S\) 枚举下一行格子的状态 \(S'\)，是指数级的；但是改成轮廓线之后，我们只需要枚举下一个格子的状态来更新就行了，分类讨论即可。复杂度直接少一个指数级。

（其实把这称作插头 DP 是不太妥当的，但大概因为插头 DP 不上轮廓线做不了吧）

【还能优化？括号表示法】

上面没提到的括号表示法，在这里讲。

我们观察到一个性质：如果有在轮廓线上顺次排列的四个插头 \(a,b,c,d\)，且 \(a,c\) 连通，\(b\) 与 \(a,c\) 都不连通，必然 \(b,d\) 不连通。

这让 我们 dxm 联想到括号序列：如果把没有插头的位置标记为空，把一个连通分量在轮廓线上靠左的插头位置标记为左括号，靠右的插头标记为右括号，沿着轮廓线，可以得到一个合法括号序列。

注意不可能一个连通块里有三个插头，因为最后所有插头都连通了，这三个插头就会形成一个回路套回路，不符合题意；也不可能有一个插头不与其他连通。

（这里说回路套回路而不是说多个回路，是因为有的题目是多个回路，但都是简单回路）

而根据括号序列，我们也能还原出轮廓线的状态。

那么我们就可以把原来的不知道多少进制压缩而成的状态，变成稳定的三进制压缩了。\(0\) 是没有插头，\(1\) 是左括号，\(2\) 是右括号。

【实现的方法】

看了上面的分析：简直太恐怖了！

首先就是怎么存储一个高进制/三进制的状态：这道题 \(n,m\le 12\)，也就是最多 \(6\) 个连通块。我们可以把六进制改存为八进制，三位三位看；三进制就变成四进制，两位两位看。

主要有两种方法：循环和记忆化广搜。记忆化广搜一般会比循环快两三倍，因为循环实际上有很多无效状态，但是如果是用广搜主动拓展出来的肯定是合法状态。

滚动数组优化：因为 \(dp[i][j][S]\) 只会用到 \(dp[i][j-1][S]/dp[i-1][m][S]\) 作为更新，可以用滚动数组；如果是记忆化广搜，就是滚动的扩展队列。

另外，用括号表示法比不用大概又快两三倍。