1、“.....因此还需要记录第行的个格子的连连通通情情况况插头插头插头连通性,连通性连通性,我们称图中的蓝线为轮廓线，任何时候只有轮廓线上方与其直接相连的格子和插头才会对轮廓线以下的格子产生直接的影响通过上面的分析，可以写出动态规划的状态表示前行，第行的个格子是否具有下插头的个位的二进制数为，第行的个格子之间的连通性为的方案总数如何表示个格子的连通性呢通常给每个格子标记个正数，属于同个的连通块的格子标记相同的数比如,和,都表示第,个格子属于个连通块，第,个格子属于个连通块为了避免出现同个连通信息有不同的表示，般会使用最小表示法种最小表示法为所有的障碍格子标记为，第个非障碍格子以及与它连通的所有格子标记为，然后再找第个未标记的非障碍格子以及与它连通的格子标记为，„„，重复这个过程，直到所有的格子都标记完毕比如连通信息,表示为,还有种最小表示法......”。

2、“.....比如上面这个例子，我们表从左到右,表示无插头,表示有插头括号内的数表示的是格子的列编号,个括号内的格子属于个连通块中国国家集训队论文长沙市雅礼中学陈丹琦第页示为,两种表示方法在转移的时候略有不同，本文后面将会提到如上图三个状态我们可以依次表示为,状态表示的优化通过观察可以发现如果轮廓线上方的个格子中个格子没有下插头，那么它就不会再与轮廓线以下的格子直接相连，它的连通性对轮廓线以下的格子不会再有影响，也就成为了冗余信息不妨将记录格子的连通性改成记录插头的连通性，如果这个插头存在，那么就标记这个插头对应的格子的连通标号，如果这个插头不存在，那么标记为这样状态就从精简为上图三个状态表示为优化后不仅状态表示更加简单，而且状态总数将会大大减少逐格递推按照从上到下，从左到右的顺序依次考虑每格分析转移完,这个格子后哪些信息对后面的决策有影响同样我们可以刻画出轮廓线，即轮廓线上方是已决策格子......”。

3、“.....直接相连的插头有个，包括个格子的下插头以及,的右插头为了保持轮廓线的连贯性，不妨从左到右依次给个格子标号，个插头标号类似地，我们需要记录与轮廓线直接相连的个插头是否存在以及个格子的连通情况通过上面的分析，很容易写出动态规划的状态,表示当前转移完,这个格子，个插头是否存在表示成个位的二进制数，以及个格子的连通性为的方案总数逐行递推的时候我们提到了状态的优化，同样地，我们也可以把格子的连通性记录在插头上，新的状态为，上图个状态依次为因为第种表示法更加直观,本文如果不作特殊说明,默认使用第种最小表示法中国国家集训队论文长沙市雅礼中学陈丹琦第页转移状态状态的转移开销主要包含两个方面每个状态转移的状态数，计算新的状态的时间逐行递推假设从第行转移到第行，我们需要枚举第行的每个格子的状态共种情况，对于任何个非障碍格子，它是否有上插头和左插头已知......”。

4、“.....状态的转移数枚举完第行每个格子的状态后，需要计算第行个格子之间的连通性的最小表示，通常可以使用并查集的数组对其重新标号或者重新执行次，时间复杂度为，最后将格子的连通性转移到插头的连通性上特别需要注意的是在转移的过程中，为了避免出现多个连通块，除了最后行，任何时候个连通分量内至少有个格子有下插头逐格递推仔细观察下面这个图，当转移到时，轮廓线上个格子只有,被改成个插头只有个插头被改动，即,的右插头修改成,的下插头和，的下插头修改成,的右插头转移的时候枚举,的状态分情况讨论般棋盘模型的逐格递推转移有类情况新建个连通分量，合并两个连通分量，以及保持原来的连通分量下面针对本题进行分析情况新建个连录所有至少有个顶点在轮廓线上的格子的连通和染色情况，即包括,在内的个格子个优化的方向扩展的状态中无效状态的总数很大程度上决定了算法的效率比如中如果出现右图的状态，那么无论之后如何决策......”。

5、“.....因此它是个无效状态对于任何个染色棋盘问题，如果从左到右有个相互不嵌套的连通块,同色同色且与,不同色，那么这个状态为无效状态小结本章介绍了解决类棋盘染色问题的般思路无论染色规则多么复杂，我们只要在基本状态即轮廓线上方与其相连的格子的连通性以及染色情况的基础上，根据题目的需要在状态中增加对以后的决策可能产生影响的信息，问题都可以迎刃而解了四类基于非棋盘模型的问题本章将会介绍类基于非棋盘模型的连通性状态压缩动态规划问题，它虽然不具有棋盘模型的特殊结构，但是解法的核心思想又跟棋盘模型的问题有着异曲同工之处嵌套的概念可以用广义的括号匹配的表示方法来理解中国国家集训队论文长沙市雅礼中学陈丹琦第页例生成树计数问题描述给你个个点的无向连通图，其边集为任何两个不同的点，如果，那么有条无向边已知和，求这个图的生成树个数，算法分析这个题给我们的第印象是非常大......”。

6、“.....连通那么如果按照,的顺序依次考虑每个点与前面的哪些点相连，并且保证任何时候都不会出现环，最后统计所有的点全部在个连通分量内的方案总数即为最终的答案在棋盘模型的问题中，我们提出了轮廓线这个概念，任何时候只有轮廓线上方与其直接相连的格子对以后的决策会产生影响类似地我们分析下这个问题，当我们确定了的所有点的连边情况后，哪些信息对以后的决策会产生影响这些点与之后的点定没有边相连，那么对以后的点的决策不会产生直接的影响，因此我们需要记录的仅仅是这个点的连通信息,如下图，我们不妨也称蓝线为轮廓线，因为只有轮廓线上的点的信息会对轮廓线右边的点的决策产生直接的影响这样我们就很容易确立状态设,表示考虑完前个点的连边情况后，这个点的连通情况为转移状态依次枚举点与这个点是否相连转移的时候需要注意这个点，任何个连通块，最多只能与其中的个点相连......”。

7、“.....那么必然与相连，这样可以避免出现孤立的连通块比如对于个的状态,来说，如果点与和相连，那么新的状态为,这样我们就可以在的时间复杂度内完成状态的转移生成树计数,中国国家集训队论文长沙市雅礼中学陈丹琦第页算法实现设表示个点的本质不同的连通情况的个数，搜索可知动态规划的时间复杂度为，依然太大可以发现当，状态,是否可以转移到,只与,有关，这样我们就可以用矩阵乘法实现动态规划加速，由于这不是本文的重点，这里不再详细介绍最终的时间复杂度为，对于,的数据规模来说已经完全可以承受了，至此问题完整解决本题中的无向图非常特殊，每个点只和距离它不超过的点有边相连，并且非常小对于棋盘模型的问题，可以抽象成个特殊的无向图个点，每个点只与它上下左右四个点有边相连那么对于个与连通性有关的无向图问题，无向图具备怎样的特点才可以用基于状态压缩的动态规划来解决分析以上几个问题......”。

8、“.....在这个序中有边相连的两个点的距离不超过很小，这样我们就可以以当前决策完序中前个，最后个点的连通性为状态作动态规划棋盘模型的问题中序即为从上到下，从左到右或从左到右，从上到下，为或，因此棋盘模型的问题和中至少有个数会非常小小结本章写得比较简略，但是依然能够给我们很多的启示处理这样的类非棋盘模型的问题，般的思路是寻找个序依次考虑每个点的决策，并分析哪些信息对以后的决策会产生影响，找到问题中的轮廓线，以轮廓线的信息来确立动态规划的状态通常来说，轮廓线上的信息比较少，这也是能够作状态压缩动态规划的基础，像本题中这样的条件往往能成为解决问题的突破口五类最优性问题的剪枝技巧基于连通性状态压缩的动态规划问题的算法的效率主要取决于状态的总数和转移的开销，减少状态总数和降低转移开销成为了优化的核心内容前面的章节我们提到了些优化的技巧......”。

9、“.....如何通过剪枝使状态总数大大减少而提高算法效率中国国家集训队论文长沙市雅礼中学陈丹琦第页例问题描述这个题目的背景是幻想游戏的中国烟花给你个的棋盘，棋盘的左边有根火柴，右边有个火箭棋盘中的每个格子可能是个空格子也可能是段管道，管道的类型有种型型型十型个火箭能够被发射当且仅当存在条由管道组成的从根点燃的火柴到这个火箭的路径给你棋盘的初始状态以及，你的目标是旋转每个格子内的管道或度，使得当点燃左边第根火柴后，被发射的火箭个数尽可能多算法分析确立状态按照从左到右，从上到下的顺序依次考虑每个格子，我们需要记录每个插头是否已经点燃以及它们之间的连通情况因此状态为,表示转移完轮廓线上个插头的连通性为把每个插头是否存在记录在中,个插头是否被点燃的进制数的状态能否达到那么最后的答案为所有可以达到的状态,中的最大值，其中表示二进制数的的个数状态转移依次枚举每个格子的旋转方式最多种......”。