$Part.1$ 插头dp

「UVA 11270」Tiling Dominoes
用$1\times2$的骨牌铺满方格，问方案数。
骨牌放置基础题，按格子转移记录左上是否有插头。

「HDU 4804」Campus Design
用$1\times2$和$1\times1$的骨牌铺满方格，问$1\times1$的骨牌个数在$c$和$d$之间的方案数。
与上一题类似，多记录一下放置了几个$1\times1$的骨牌。

「HDU 1693」Eat the Trees
用若干回路完全覆盖网格方案数，只需生成和合并成对插头。

「ZOJ 4231」The Hive II
用若干回路完全覆盖六边形网格方案数，和上一题类似。

「Ural 1519」Formula 1
用一条回路覆盖网格方案数，回路的闭合只能出现在最后一个格子。

「POJ 1739」Tony’s Tour
用一条路径覆盖网格方案数，起点终点固定，可以在外面加一圈限制变成一条回路问题。

「USACO 6.1.1」Postal Vans
用一条回路覆盖网格方案数，$m$很小$n$很大，矩阵快速幂+高精度。

「HNOI2007」神奇游乐园
网格图，每个格子有权值，找一条最大权回路，不要求覆盖所有格子，意味着回路可以在任何格子闭合。

「ProjectEuler 393」Migrating ants
用若干有向回路覆盖网格的方案数，$k$条无向回路覆盖的贡献是$2^k$，多加一个域记录回路闭合次数。

「ZOJ 3213」Beautiful Meadow
网格图，每个格子有权值，找一条最大权不自交路径，多加一个域记录独立插头的生成与消失次数。

「CQOI 2017」矩形
将网格染色成黑白两部分，每部分都与边界连通的方案数。
钦定左上角是黑色，这样只需要白色与边界相连，当轮廓线颜色全部是A，上方放过B，再要放A时不合法。

「UVA 10572」Black & White
将网格染色成黑白两部分，且不存在$2\times2$同色的方案数，输出方案。
除了轮廓线之外，再记录当前格子左上角颜色即可。
对于输出方案，记录$pre_{i,j,x}$和$op_{i,j,x}$表示格子$(i,j)$从上一格的哪个状态转移过来，以及这格放什么颜色，逆推回去即可。

「JLOI 2009」神秘的生物
网格图，每个格子有权值，找一个最大权连通块。
多开一个域记录是否有连通分量与外界完全隔绝。

「NOI 2007」生成树计数
问一类特殊的图的生成树个数，其实并不是传统意义上的插头dp，但用到了最小表示法，思想类似。
最小表示法，对状态编号+矩阵快速幂。

「2015 ACM-ICPC Asia Shenyang Regional Contest - Problem E」Efficient Tree
求网格图的最小生成树个数，以及所有最小生成树的$\Pi_{LRdeg(u)}$之和，$LUdeg(u)$定义为节点$u$与左边和上边的节点中和$u$相连的节点的个数$+1$。
每个点只考虑向左上连边，注意不能成环，且不能孤立连通分量，连通分量被孤立当且仅当上方节点所在连通分量在轮廓线上只出现一次，且当前节点不与上方节点连边。

「HDU 4113」Construct the Great Wall
网格图，沿着格边的一条回路，把所有的O圈在里面，X隔在外面，求回路的最小长度。
一个格子在回路内部当前仅当他左侧有奇数个插头，在回路外部当且仅当左侧有偶数个插头，仅在合法时转移。

「HDU 4796」Winter’s Coming
网格图，找一条最小权路径连通上下边界，且所有W在路径左侧，L在路径右侧。
一个格子在路径左侧当前仅当他左侧有偶数个插头，在路径右侧当且仅当左侧有奇数个插头，仅在合法时转移。
独立插头只能在第一行生成，在最后一格判断已经生成过独立插头且轮廓线上仅有一个插头则合法。

「ZOJ 2125」Rocket Mania
网格图，每个格子是’.’,’+’,’L’,’T’,’-‘中的一种，可以旋转，问右侧最多几行和左侧的第d行相连。
首先把图旋转，让左右变成上下，把与上边第k列相连的插头钦定为1，只能在制定格子生成1插头，其余插头使用最小表示法表示，然后分类讨论每种格子每种放置方法的转移。
有一个减少状态数的小trick，一个非1的插头在轮廓线上只出现一次，那他就没用了，直接视作0。

「ZOJ 2126」Rocket Mania Plus
同上，问右侧最多几行和左侧相连。
可以在第一列任何格子生成1插头。

「World Finals 2009/2010 Harbin」Channel
网格图找一条从左上到右下的最长路径，使得路径在拐角处八连通意义上不相邻，且不能存在$2\times2$都是路径的块，输出方案。
输出方案和「UVA 10572」Black & White类似。
除了记录插头之外还需要记录每个格子是否有路径，因为存在路径也可能没有插头。
考虑拐角处八连通意义不相邻怎么处理，需要记录当前格子左上以及右上两个格子，右上在轮廓线上可以直接知道，左上不在轮廓线上，当在上一格处他在轮廓线上，额外记录即可。当生成成对的右下插头时左上不能有路径，当左插头延伸到下插头时右上不能有路径。

「HDU 3958」Tower Defence
网格图给定起点终点，图上有若干障碍物，再放置若干障碍物最大化起点到终点的最短路。
同上一题，只不过没有拐角处不能八连通的限制，对于输出方案，把所有不是路径的格子全放上障碍物。

「UVA 1214」Manhattan Wiring
网格图，有一对2一对3，两条路径连接相同数字，路径不相交，最化小路径长度和。
不需要最小表示法，插头直接生成2和3即可，自环一定会使答案不优，不需要判。

「SDOI 2014」电路板
同上，但最多有九对需要相连的数字，且一个格子可以有两根线，具体见题目。

「SPOJ CAKE3」Delicious Cake
给一个网格蛋糕，延网格的边切分分成若干块，问方案数。
考虑染色模型，但有个问题，合并两个相邻的连通分量是不合法的，看到$n$很小，可以直接把连通分量两两之间相邻与否压入状态。

「AIZU 2452」Pipeline Plans
有若干种瓷砖，每种有若干个，不可以旋转，问有多少种放置方式让左上和右下格子中心点连通。
将每种瓷砖剩余个数压入状态，分类讨论转移即可，统计方案可以在转移至最后一格时统计，比较方便。

「Atcoder TDPC」マス目
网格图，黑白染色，使得左上角和右下角同属一个黑色连通块的方案数。
将与左上角连通的黑色连通分量即为1，其余使用最小表示法即可。
也可以多开一个域表示当前哪个编号的连通分量和左上角相连。