插头DP 简易笔记
插头DP有什么用？
插头DP是用来解决一类网格图上的连通性问题的强力工具。题目的特征是给定的网格非常小（这个特征类似状压DP）。事实上，插头DP也可以看做是状压DP的一种
基本要素
轮廓线
我们DP时，是自上而下、自左向右来考虑的，因此，我们需要有一条线，来划分已经考虑的和尚未考虑的部分。下图的黄线就是i=3,j=3时的轮廓线（i,j是指目前正在考虑的格子，即图中的蓝色格子）
插头
插头表示格子之间的连通性
比如格子(i,j)与格子(i,j+1)连通，那么(i,j)就有一个右插头，(i,j+1)就有一个左插头
注意插头一定是成对存在的，它是一种实际状态，即两个格子之间确实连通了，并不是一种“将要连通过去”的虚拟状态。简单的说，产生一对插头，必须要有两个格子“两情相悦”
轮廓线的状态
这是插头DP的重点！
假如网格是n*m的，那么轮廓线的长度就是(m+1)，轮廓线两侧分别是已考虑和未考虑的部分，而轮廓线每一位的状态就是指已考虑一侧格子是否有插头通向未考虑一侧的格子
通过一道例题来感受一下轮廓线的状态：【bzoj1814】Ural 1519 Formula 1
一句话题意：一个 m * n 的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。
容易看出，本题轮廓线上的插头一定是偶数个，我们可以让插头两两配对
于是我们将轮廓线上的插头分为两类：左括号插头和右括号插头
两个插头配对，当且仅当：当前状态下，在已考虑部分中，这两个插头所在格子已经连通
举一个状态的例子：
图中蓝线就是已考虑部分的一种可能的连通情况（也包括了轮廓线的插头情况），那么此时轮廓线的状态就是：(0)(0)
我们可以用三进制来表示轮廓线状态，0表示没有插头，1表示左插头，2表示右插头
三进制的运算非常慢，我们把它变成四进制，然后就可以进行位运算了
那么轮廓线的连通情况，状态最大值会高达4^(m+1)，把m=12代入计算就是67108864，如果要开那么大的数组，显然空间爆炸。幸运的是，在所有情况中，有效情况的数量其实只有20万左右，因此我们可以开一个20万的数组，然后搞一个蛤希表来对有效状态编号
当然，有一些题目不一定要求插头两两配对，比如Park II那道题，具体情况具体分析吧
状态转移与答案更新
这个部分每道题都有所不同，还是去看具体的题目吧，建议先看上面提到的那道例题
通法就是分类讨论，最简单的题目（也就是上面那道例题）是分7种情况讨论。当然，还有要你分上十种情况讨论的毒瘤题。掌握了通法其实也不难，但思维一定要缜密，不能漏掉某种情况