插头 DP
定义
有些 状压 DP 问题要求我们记录状态的连通性信息，这类问题一般被形象的称为插头 DP 或连通性状态压缩 DP。例如格点图的哈密顿路径计数，求棋盘的黑白染色方案满足相同颜色之间形成一个连通块的方案数，以及特定图的生成树计数等等。这些问题通常需要我们对状态的连通性进行编码，讨论状态转移过程中连通性的变化。
引入
骨牌覆盖与轮廓线 DP
温故而知新，在开始学习插头 DP 之前，不妨先让我们回顾一个经典问题。
题目大意：在
当
另一种划分阶段的方法是逐格 DP，或者称之为轮廓线 DP。
虽然逐格 DP 中我们的状态增加了一个维度，但是转移的时间复杂度减少为
观察到这里不放和竖放的方程可以合并。
题目大意：给定 E 或 S。
对于一个矩阵，有一个计分方案。按照行优先的规则扫描每个格子，如果这个格子之前被骨牌占据，则 skip。
否则尝试放多米诺骨牌。如果放骨牌的方向在矩阵外或被其他骨牌占据，则放置失败，切换另一种方案或 skip。
如果是 E 则优先放一个 S 则优先放一个
术语
阶段：动态规划执行的顺序，后续阶段的结果只与前序阶段的结果有关（无后效性）。很多 DP 问题可以有多种划分阶段的方式。例如在背包问题中，我们通常既可以按照物品划分阶段，也可以按照背包容量划分阶段（外层循环先枚举什么）。而在多米诺骨牌问题中，我们可以按照行、列、格子以及对角线等特征划分阶段。
轮廓线：已决策状态和未决策状态的分界线。
插头：一个格子某个方向的插头存在，表示这个格子在这个方向与相邻格子相连。
路径模型
多条回路
例题
题目大意：求用若干条回路覆盖
严格来说，多条回路问题并不属于插头 DP，因为我们只需要和上面的骨牌覆盖问题一样，记录插头是否存在，然后成对的合并和生成插头就可以了。
注意对于一个宽度为 roll()。
习题
题目大意：同上题，但格子变成了六边形。
一条回路
例题
题目大意：求用一条回路覆盖
在上面的状态表示中我们每合并一组连通的插头，就会生成一条独立的回路，因而在本题中，我们还需要区分插头之间的连通性（出现了！）。这需要我们对状态进行额外的编码。
状态编码
通常的编码方案有括号表示和最小表示，这里着重介绍泛用性更好的最小表示。我们用长度
那么下面两组编码方式表示的是相同的状态：
0 3 1 0 1 30 1 2 0 2 1
我们将相同的状态都映射成字典序最小表示，例如在上例中的 0 1 2 0 2 1 就是一组最小表示。
我们用 b[] 数组表示轮廓线上插头的状态。bb[] 表示在最小表示的编码的过程中，每个数字被映射到的最小数字。注意
我们注意到插头总是成对出现，成对消失的。因而 0 1 2 0 1 2 这样的状态是不合法的。合法的状态构成一组括号序列，实际中合法状态可能是非常稀疏的。
手写哈希
在一些 状压 DP 的问题中，合法的状态可能是稀疏的（例如本题），为了优化时空复杂度，我们可以使用哈希表存储合法的 DP 状态。对于 C++ 选手，我们可以使用 std::unordered_map，当然也可以直接手写，这样可以灵活的将状态转移函数也封装于其中。
上面的代码中：
MaxSZ表示合法状态的上界，可以估计，也可以预处理出较为精确的值。Prime一个小于MaxSZ的大素数。head[]表头节点的指针。next[]后续状态的指针。state[]节点的状态。key[]节点的关键字，在本题中是方案数。clear()初始化函数，和手写邻接表类似，我们只需要初始化表头节点的指针。push()状态转移函数，其中d是一个全局变量（偷懒），表示每次状态转移所带来的增量。如果找到的话就+=，否则就创建一个状态为s，关键字为d的新节点。roll()迭代完一整行之后，滚动轮廓线。
关于哈希表的复杂度分析，以及开哈希和闭哈希的不同，可以参见 《算法导论》 中关于散列表的相关章节。
状态转移
习题
题目大意：求用一条回路覆盖
题目大意：一个
题目大意：一个
题目大意：求用一条有向回路覆盖
题目大意：用多条回路覆盖
一条路径
例题
题目大意：一个
本题是标准的一条路径问题，在一条路径问题中，编码的状态中还会存在不能配对的独立插头。需要在状态转移函数中，额外讨论独立插头的生成、合并与消失的情况。独立插头的生成和消失对应着路径的一端，因而这类事件不会发生超过两次（一次生成一次消失，或者两次生成一次合并），否则最终结果一定会出现多个连通块。
我们需要在状态中额外记录这类事件发生的总次数，可以将这个信息编码进状态里（注意，类似这样的额外信息在调整轮廓线的时候，不需要跟着滚动），当然也可以在 hashTable 数组的外面加维。下面的范例程序中我们选择后者。
状态转移
习题
题目大意：
-
第 i 个参观的格点 (x, y)，满足 T[x][y]= L[i]
-
路径的一端在棋盘的边界上
求可行的方案数。
染色模型
除了路径模型之外，还有一类常见的模型，需要我们对棋盘进行染色，相邻的相同颜色节点被视为连通。在路径类问题中，状态转移的时候我们枚举当前路径的方向，而在染色类问题中，我们枚举当前节点染何种颜色。在染色模型中，状态中处在相同连通性的节点可能不止两个。但总体来说依然大同小异。我们不妨来看一个经典的例题。
例题「UVA 10572」Black & White
题目大意：在
状态编码
我们先考虑状态编码。不考虑连通性，那么就是 SGU 197. Nice Patterns Strike Back，不难用 状压 DP 直接解决。现在我们需要在状态中同时体现颜色和连通性的信息，考察轮廓线上每个位置的状态，二进制的每 Offset 位描述轮廓线上的一个位置，因为只有黑白两种颜色，我们用最低位的奇偶性表示颜色，其余部分示连通性。
考虑第一行上面的节点，和第一列左侧节点，如果要避免特判的话，可以考虑引入第三种颜色区分它们，这里我们观察到这些边界状态的连通性信息一定为 0，所以不需要对第三种颜色再进行额外编码。
在路径问题中我们的轮廓线是由
这样的编码方案中依然保留了很多冗余信息，（连通的区域颜色一定相同，且左上角的格子只需要颜色信息不需要连通性），但是因为已经用了哈希表和最小表示，对时间复杂度的影响不大，为了降低编程压力，就不再细化了。
在最多情况下（例如第一行黑白相间），每个插头的连通性信息都不一样，因此我们需要 Offset 为
手写哈希
因为需要构造任意一组方案，这里的哈希表我们需要添加一组域 pre[] 来记录每个状态在上一阶段的任意一个前驱。
方案构造
有了上面的信息，我们就可以容易的构造方案了。首先遍历当前哈希表中的状态，如果连通块数目不超过 pre 数组构造出方案，注意每一行的末尾因为我们执行了 Roll() 操作，颜色需要取 c[j+1]。
状态转移
我们记：
cc当前正在染色的格子的颜色lf左边格子的颜色up上边格子的颜色lu左上格子的颜色
我们用
对于最后一种情况需要注意的是，如果已经生成了一个封闭的连通区域，那么我们不能再使用她的颜色染色，否则这种颜色会出现两个连通块。我们似乎需要额度记录这种事件，可以参考 「ZOJ 3213」Beautiful Meadow 中的做法，再开一维记录这个事件。不过利用本题的特殊性，我们也可以特判掉。
进一步讨论连通块消失的情况。每当我们对一个格子进行染色后，如果没有其他格子与其上侧的格子连通，那么会形成一个封闭的连通块。这个事件仅在最后一行的最后两列时可以发生，否则后续为了不出现
2 2
o#
#o我们特判掉这种情况，这样在本题中，就可以偷懒不用记录之前是否已经生成了封闭的连通块了。
习题
题目大意：给一个棋盘图，每个格子有权值，求权值之和最小的连通块。
题目大意：给一个棋盘图，每个格子有权值，求权值之和最大的连通块。
图论模型
题目大意：某类特殊图的生成树计数，每个节点恰好与其前
题目大意：给出一个
你需要求出：最小生成树的边权和，以及所有最小生成树的得分之和。
（
实战篇
例题
题目大意：在 x 和 o。
有一类插头 DP 问题要求我们在棋盘上构造一组墙，以分割棋盘上的某些元素。不妨称之为修墙问题，这类问题既可视作染色模型，也可视作路径模型。
在本题中，如果视作染色模型的话，不仅需要额外讨论染色区域的周长，还要判断在角上触碰而导致不合法的情况（图 2）。另外与 「UVA 10572」Black & White 不同的是，本题中要求围墙为简单多边形，因而对于下面的回字形的情况，在本题中是不合法的。
3 3
ooo
oxo
ooo因而我们使用路径模型，转化为 一条回路 来处理。
我们沿着棋盘的交叉点进行 DP（因而长宽需要增加 x 在回路之外，o 在回路之内。因此我们还需要维护当前位置是否在回路内部。对于这个信息我们可以加维，也可以直接统计轮廓线上到这个位置之前出现下插头次数的奇偶性（射线法）。
习题
题目大意：在
题目大意：-,T,L,+ 型或没有），可以把管道旋转 0°,90°,180°,270°, 问地图最多能有几行的右边界与第 X 行的左边界通过管道相连。
题目大意：-,T,L,+ 型或没有），可以把管道旋转 0°,90°,180°,270°, 问地图最多能有几行的右边界与左边界通过管道相连。
题目大意：一张方格地图上用 . 表示空地、# 表示石头，找到最长的一条路径满足：
- 起点在左上角，终点在右下角。
- 不能经过石头。
- 路径自身不能在八连通的意义下成环。（即包括拐角处也不能接触）
题目大意：可以转化为求解一条从
题目大意：有一个
题目大意：现有一共 12 种图案的瓷砖，每种瓷砖数量给定。要求铺到一块可视为
题目大意：一块
题目大意：一块可视为
本章注记
插头 DP 问题通常编码难度较大，讨论复杂，因而属于 OI/ACM 中相对较为 偏门的领域。这方面最为经典的资料，当属 2008 年 陈丹琦 的集训队论文——基于连通性状态压缩的动态规划问题。其次，HDU 的 notonlysuccess 2011 年曾经在博客中连续写过两篇由浅入深的专题，也是不可多得的好资料，不过现在需要在 Web Archive 里考古。
多米诺骨牌覆盖
「HDU 1400」Mondriaan’s Dream 也出现在 《算法竞赛入门经典训练指南》 中，并作为《轮廓线上的动态规划》一节的例题。多米诺骨牌覆盖（Domino tiling） 是一组非常经典的数学问题，稍微修改其数据范围就可以得到不同难度，需要应用不同的算法解决的子问题。
当限定
当
当
- 「51nod 1031」骨牌覆盖
- 「51nod 1033」骨牌覆盖 V2|「Vijos 1194」Domino
- 「51nod 1034」骨牌覆盖 V3|「Ural 1594」Aztec Treasure
- Wolfram MathWorld, Chebyshev Polynomial of the Second Kind
一条路径
「一条路径」是 哈密顿路径（Hamiltonian Path） 问题在 格点图（Grid Graph） 中的一种特殊情况。哈密顿路径的判定性问题是 NP-complete 家族中的重要成员。Niconico 上有一个『フカシギの数え方』おねえさんといっしょ！みんなで数えてみよう（和大姐姐一起学习计算系列）的科普向视频，就使用这个问题作为例子，来说明 NPC 问题的计算时间如何随着问题的规模的线性增长而指数增长。
