//主要摘抄自参考资料2333
最优性原则&&无后效性 最优子结构
状态的转移开销主要包含两个方面：每个状态转移的状态数，计算新的状态的时间．
保证从已经更新的状态转移过来 bool?
考虑等效转化，使决策没有后效性，如骨牌覆盖往下放转化为往上放，往右转化为往左。同时将状态变为\((i,j)\)是否覆盖
考虑优化，横纵置换？
考虑删除亢余状态，同一个阶段明显。。删除
DP出现两种要统计的
一个作为状态的一维，一个作为内容
设两个独立的函数——基本不用
集合内元素作为状态，一般在数据规模较小时适用，时间复杂度一般为指数级别。一般二进制压位表示集合
例题：[GD012014]拯救莫莉斯
? POJ Corn Fields
? POJ 炮兵阵地
与连通性有关或者蕴含连通信息，基于状压基础？
状态：阶段，连通性，插头
轮廓线已决策格子和未决策格子的分界线
插头表示各自可以在这个方向与外界相连【二进制记录是否有与这条轮廓线相连的插头】
连通信息最小表示法：最左边格子为标记，给连通块编序号
Ural 1519 Formula 1
影响行转移的变量：行数、下插头数决定下一行上插头、连通性
设计状态\(f(i,S,C)\)，\(S\)代表下插头状态，\(C\)代表联通性
转移：对每个状态通过指数时间枚举下行插头状态，再暴力维护可行性和连通性。
从第\(i\)行转移到第\(i+1\)行，\(i+1\)行的格子有六种情况的插头
==状态转移数<=2^n???==
用搜索或并查集计算连通性
发现同行某些列，没有下插头时，对下一行不造成影响，是冗余信息，
改进状态为\(f(i,C)\)，只保存下插头的连通性\(C\)。
同样把格子的连通性记录在插头上\(f(i,j,C)\)表示格子\((i,j)\)的指向它的轮廓线的
插头的连通状态
情况1 新建一个连通分量，这种情况出现在\((i, j)\)有右插头和下插头．
新建的两个插头连通且不与其它插头连通，
这种情况下需要将这两个插头连通分量标号标记成一个未标记过的正数，重新\(O(n)\)扫描保证新的状态满足最小表示．
情况2 合并两个连通分量，这种情况出现在\((i, j)\)有上插头和左插头．
如果两个插头不连通，那么将两个插头所处的连通分量合并，标记相同的连通块标号，\(O(n)\)扫描保证最小表示；
如果已经连通，相当于出现了一个回路，这种情况只能出现在最后一个非障碍格子．
情况3 保持原来的连通分量，这种情况出现在\((i, j)\)的上插头和左插头恰好有一个，下插头和右插头也恰好有一个．下插头或右插头相当于是左插头或上插头的延续，连通块标号相同，并且不会影响到其他的插头的连通块标号，计算新的状态的时间为\(O(1)\)．
注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线需要特殊处理．
值得一提的是，上面三种情况计算新的状态的时间分别为\(O(n),O(n),O(1)\)，
如果使用前面提到的第二种最小表示方法，情况1只需要\(O(1)\)，但是情况3可能需要重\(O(n)\)新扫描．
逐行递推的每一个转移的状态总数为指数级，而逐格递推为\(O(1)\)，
每次计算新的状态的时间两者最坏情况都为\(O(n)\)，逐行递推自带常数大【雾
[ 1 ] 直接位运算编码： 状态压缩将\(C\)压成\((p+1)\)进制数，\(p\)代表可能出现的最多连通块数，根据题意满足\(p\leq \lfloor n/2 \rfloor\)，且一般取\((p+1)\)为\(2\)的幂次，方便进行位运算【不用进行快速幂】
如需大范围修改连通块标号，最好预先将状态\(O(n)\) 解码到一个数组中，修改后再\(O(n)\)计算出新的\(p\)进制数；==//存疑==
而对于只需要局部修改几个标号的情况下，可以直接用\(\lfloor x/p^{i-1} \rfloor mod p\)来获取第i位的状态，用\(\pm k \times p^{i-1}\)直接对第\(i\)位进行修改．
[ 2 ] 预编码：将所有连通性状态搜索出来，并预先标号为\(0,…,tot\)，之后状态\(f(i,j,k)\)就表示在第\(i\)行第\(j\)列编号为\(k\)的连通性状态。
[ 3 ] hash编码： 通过hash将连通性状态映射至一个较小的空间上，与预编码一样都是为了消除直接编码中的冗余状态。
预编码可以在解码时结合hash table食用。
==记忆化宽度优先搜索==
?因为是哈密顿回路，插头两两匹配，且不交叉。【如果交叉，可得两个连通块可以合并为一个，矛盾】
每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态．
【1】陈丹琦《基于连通性状态压缩的动态规划问题》
原文：https://www.cnblogs.com/bobble/p/9398485.html