笔记汇总
之前所讲的状压$DP$是不完全的，现在补全。
Hamilton路径，是常见的$NP$类问题，在这样一个图上跑状压$DP$，属于集合式状压。
连通性$DP$的状态压缩表示的是每个点的 位置关系，
集合类$DP$的状态压缩表示的是每个点的 是否存在
我们知道它的初始及目标，那中间过程也应有较小的初始及目标。
为了避免写图论，以及路径缺漏重复，我们将初始到任意一点的所有路径视为集合，
基础是不重复的，由归纳知所有路径也不会缺漏重复，证必 qwq。
回归插头。
由于我们直接将部分点暴力压缩，阶段间的状态复杂度过大，故而提出了按格枚举的插头$DP$。
简单来说，就是一个拼图，但为了避免原来与新的部分可能性过多，故多用于 限制较少的连通性 $DP$ 问题。
即同时满足容易判断所受限制（多米诺覆盖），新部分 可能状态数 较少。
个人不建议将它与轮廓线$DP$分开理解，或许可以叫拼图$DP$。
我们不需要存下全图的状态表示，仅需要存下可能影响答案的哪些状态表示（已知与未知的桥梁）。
插头$DP$在判断一个格子是否与连通块相连方面，有两种表示方法。
以连通块数量为编号的 最小表示法。
以块上类型为编号的 括号表示法，满足 两两配对、路径间不可交叉（具体分析）
一般复杂度远小于预估最坏复杂度，但空间复杂度略高。
插头$DP$ 的难点是状态分析，一般包括
$[$ 格点状态 $×$ 邻入边状态 $×$ 邻出边状态$][$格点 $,$ 邻入边 $,$ 邻出边不矛盾 $]$
在同时你还需要维护更新原连通块的编号信息，算是很难的了。
记得 哈希表 $+$ 滚动数组 $+$ 有效性优化
