插头dp学习笔记
插头DP是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。本文以P5056【模板】插头dp为例进行分析。
一个格子有四个插头，上下左右，就像拼图凸出来和凹进去的地方。一个格子会选出两个插头，形成一条经过此格的路径。当两个左右在一起的格子，左边的格子选了右插头，右边的格子选了左插头，那么这两个格子就是联通的了。
压缩的状态表示的是一条轮廓线上方格子选择的插头的信息。这条轮廓线是已决策的格子与未决策的格子间形成的边界线，当前要转移的格子正好在这条边界线的弯折处。状态则描述的是这条轮廓线上方的格子的插头与轮廓线相交的信息，用三进制表示向下、向上和无。必须要记录向上和向下的方向信息，因为这样才能确保组成有效的联通分类。
状态采用括号表示法。在计算过程中，任意连通分量一定会与轮廓线有两个交点，不然的话此联通分量就已经是一条闭环了，不满足题意。我们规定在记录时，这两个交点中靠左的插头方向向下，搞右的插头方向向上，状态压缩成三进制的1和2。并且1和2在轮廓线上的分配一定与左右括号的分配完全一致，因为如果有相交情况的话，路径就不是一条回路了。所以可以用括号匹配的方法确定所有的联通分量。
可以这样抽象理解一下状态的表示。一群工人要把水管修成一条回路，尚未完工的时候，他们造了许多不同的联通分量。他们其实不需要知道这些联通分量的路径到底是怎样的，只需要知道他们现在面对的这些水管的切面中，哪个切面与哪个切面是本来就联通的。最后的答案是最后一个格子算完后只有一个联通分量的情况的个数。
状态的转移需要分多种情况讨论：
- 当前格子的上面和左面都没别的格子的插头。我们要新建一个联通分量，状态改变是把本来是两个0的相邻数位分别改成1和2。第一个格子一定是这种情况。
- 当前格子有上插头或者左插头的其中一个。我们要保持原有的联通分量，状态的改变是新建一个与收到的上或左插头方向一样的插头。
- 当前格子的上面和左面都有别的格子的插头。我们要合并两个联通分量。因为合并会涉及到插头方向的改变，所以这里需要分类讨论然后用括号匹配找到对应插头。
- 第一种{1,1,(2,2)}，意思是两个要合并的联通分量 的插头分布是向下、向下、向上和向上，其中和两个是要合并的。注意这只表示他们之间的顺序，两个插头之间可能夹杂着别的无关插头。要改变成{1,2,0,0}，方法是用括号匹配找到第一个2所对应的那个1，将其变成2，然后两个2都变成0。
- 第二种是{(1,1),2,2}=>{0,0,1,2}。
- 第三种是{1,(2,1),2}=>{1,0,0,2}。
- 最后一种是{1,2}，也就是一个联通分类的两个插头相遇了，如果合并的话就会形成一条闭环，所以这种情况只有在最后的格子上才能合并。
参考资料：https://www.luogu.com.cn/problem/solution/P5056
图片来源于：洛谷用户GNAQ
投递牛客等公司7个岗位 >
