插头dp

插头dp是什么，这里只有插头

在状态压缩动态规划中，有一类是需要记录若干个元素的联通情况，称之为基于连通性状态压缩的动态规划，也就是插头 dp

在大部分棋盘状压 dp 中，状态划分可以依据行或列进行划分，行列之间相对独立，但有时却不行，例如让你在棋盘中对联通块进行操作，下图的联通块是无法用上述的方法去记录的

这时便不能采用上述做法，只能考虑新做法

先讲几个概念

1.插头：对于一个4连通的问题来说，它通常有上下左右4个插头，一个方向的插头存在表示这个格子在这个方向可以与外面相连

2.轮廓线：已决策状态和未决策状态的分界线

考虑一题

给出 \(n\times m\) 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？（P5056）

我们发现一个格子若在联通块内，则 4 个插头恰好有 2 个插头存在，即从一个格子进来，另一个格子出去，考虑一种逐格递推形式，则轮廓线会发生如下变化

考虑轮廓线应记录插头，分析一下轮廓线上的插头位置

这很好理解，轮廓线一下是未决策的点，已经决策的点都可以向未决策的点有一个插头

这已经很好的给出了状态转移方程的思路，令 \(dp_{i,j,S_0}\) 为到了 第 \(i\) 行，第 \(j\) 列，所有插头状态为 \(S_0\)

考虑 \(S_0\) 如何记录，如何表示
，先考虑回路的特点

以上图为例，轮廓线上方是由若干条互不相交的路径构成的，而每条路径的两个端口恰好对应了轮廓线上的两个插头，一条路径上的所有格子对应的是一个连通块，而每条路径的两个端口对应的两个插头是连通的而且不与其他任何一个插头连通，也就是说，在任何时候每一个连通分量恰好有2个插头，在考虑一条性质

轮廓线上从左到右4个插头 \(a,b, c, d\)，如果 \(a, c\) 连通，并且与 \(b\) 不连通，那么 $ b, d$ 一定不连通

证明引用陈丹琦的论文

“两两匹配”，“不会交叉”这样的性质，我们很容易联想到括号匹配，则一条轮廓线之间，左插头一定可以与右插头一一对应，那么考虑一种括号表示法，用0表示无插头，1表示左括号插头，2表示右括号插头来记录下所有的轮廓线信息

这样，状态的储存也表示完毕，考虑如何转移，按格转移，令 \((i,j-1)\) 的右插头为 \(p\)，\((i-1, j)\) 的下插头为 \(q\)，$ (i, j)$ 的下插头为 \(x\)，右插头为 \(y\),每次转移就是将 \(p\) ,\(q\) 改为 \(x\) ,\(y\)

1.\((i,j)\) 为障碍，显然不能有插头，即只有 \(p=0,q=0\) 才能转移至 \(x=0,y=0\)

2.新建一个插头，即 \(p,q=0\) 时令 \(x=1,y=2\)

3.只有向右插头，即 \(p\) 不为 \(0\) 且 \(q\) 为 \(0\) 时，由于没有可接的插头，只能将右插头延伸,可直走可拐弯，即 \(x=1,y=0\) 或 \(x=2,y=0\)

4.只有向下插头，同上，令 \(x=0,y=1\) 或 \(x=0,y=2\)

5.向右为左插头，向下为右插头，考虑从插头建立到最后闭合，显然是一个闭合回路，这种情况只能在最后一次转移出现，也只有这种情况能计入答案

6.向右为右插头，向下为左插头，则合并插头之后，该右插头对应的左插头和该左插头对应的右插头在消掉之后恰好匹配，也不需要执行其他改动，即令 \(x=0,y=0\)

7.两个都是右插头，在合并之后应将两个右插头对应的左插头设为匹配

8.两个都是右插头，在合并之后应将两个左插头对应的右插头设为匹配