度为，最后将格子的连通性转移到插头的连通性上特别需要注意的是在转移的过程中，为了避免出现多个连通块，除了最后行，任何时候个连通分量内至少有个格子有下插头逐格递推仔细观察下面这个图，当转移到时，轮廓线上个格子只有，被改成个插头只有个插头被改动，即，的右插头修改成，的下插头和，的下插头修改成，的右插头转移的时候枚举，的状态分情况讨论般棋盘模型的逐格递推转移有类情况新建个连通分量，合并两个连通分量，以及保持原来的连通分量下面针对本题进行分析情况新建个连录所有至少有个顶点在轮廓线上的格子的连通和染色情况，即包括，在内的个格子个优化的方向扩展的状态中无效状态的总数很大程度上决定了算法的效率比如碍格子，它是否有上插头和左插头已知，因此最多只有种情况，状态的转移数枚举完第行每个格子的状态后，需要计算第行个格子之间的连通性的最小表示，通常可以使用并查集的数组对其重新标号中学陈丹琦第页转移状态状态的转移开销主要包含两个方面每个状态转移的状态数，计算新的状态的时间逐行递推假设从第行转移到第行，我们需要枚举第行的每个格子的状态共种情况，对于任何个非障，上图个状态依次为因为第种表示法更加直观，本文如果不作特殊说明，默认使用第种最小表示法中国国家集训队论文长沙市雅礼连通性为的方案总数逐行递推的时候我们提到了状态的优化，同样地，我们也可以把格子的连通性记录在插头上，新的状态为的个插头是否存在以及个格子的连通情况通过上面的分析，很容易写出动态规划的状态，表示当前转移完，这个格子，个插头是否存在表示成个位的二进制数，以及个格子的线直接相连的格子有个，直接相连的插头有个，包括个格子的下插头以及，的右插头为了保持轮廓线的连贯性，不妨从左到右依次给个格子标号，个插头标号类似地，我们需要记录与轮廓线直接相连会大大减少逐格递推按照从上到下，从左到右的顺序依次考虑每格分析转移完，这个格子后哪些信息对后面的决策有影响同样我们可以刻画出轮廓线，即轮廓线上方是已决策格子，下方是未决策格子由图可知与轮廓号，如果这个插头不存在，那么标记为这样状态就从精简为上图三个状态表示为优化后不仅状态表示更加简单，而且状态总数将它就不会再与轮廓线以下的格子直接相连，它的连通性对轮廓线以下的格子不会再有影响，也就成为了冗余信息不妨将记录格子的连通性改成记录插头的连通性，如果这个插头存在，那么就标记这个插头对应的格子的连通标后面将会提到如上图三个状态我们可以依次表示为，状态表示的优化通过观察可以发现如果轮廓线上方的个格子中个格子没有下插头，那么表从左到右，表示无插头，表示有插头括号内的数表示的是格子的列编号，个括号内的格子属于个连通块中国国家集训队论文长沙市雅礼中学陈丹琦第页示为，两种表示方法在转移的时候略有不同，本文，重复这个过程，直到所有的格子都标记完毕比如连通信息，表示为，还有种最小表示法，即个连通块内所有的格子都标记成该连通块最左边格子的列编号，比如上面这个例子，我们出现同个连通信息有不同的表示，般会使用最小表示法种最小表示法为所有的障碍格子标记为，第个非障碍格子以及与它连通的所有格子标记为，然后再找第个未标记的非障碍格子以及与它连通的格子标记为，„„性为的方案总数如何表示个格子的连通性呢通常给每个格子标记个正数，属于同个的连通块的格子标记相同的数比如，和，都表示第，个格子属于个连通块，第，个格子属于个连通块为了避免连的格子和插头才会对轮廓线以下的格子产生直接的影响通过上面的分析，可以写出动态规划的状态表示前行，第行的个格子是否具有下插头的个位的二进制数为，第行的个格子之间的连通插头连接成了个连通块，因此还需要记录第行的个格子的连连通通情情况况插头插头插头连通性，连通性连通性，我们称图中的蓝线为轮廓线，任何时候只有轮廓线上方与其直接相我们需要记录第行的每个格子是否有下插头，这决定了第行的每个格子是否有上插头仅仅记录插头是否存在是不够的，可能导致出现多个回路如右图，而本题要求个回路，也就隐含着最后所有的非障碍格子通过插我们需要记录第行的每个格子是否有下插头，这决定了第行的每个格子是否有上插头仅仅记录插头是否存在是不够的，可能导致出现多个回路如右图，而本题要求个回路，也就隐含着最后所有的非障碍格子通过插头连接成了个连通块，因此还需要记录第行的个格子的连连通通情情况况插头插头插头连通性，连通性连通性，我们称图中的蓝线为轮廓线，任何时候只有轮廓线上方与其直接相连的格子和插头才会对轮廓线以下的格子产生直接的影响通过上面的分析，可以写出动态规划的状态表示前行，第行的个格子是否具有下插头的个位的二进制数为，第行的个格子之间的连通性为的方案总数如何表示个格子的连通性呢通常给每个格子标记个正数，属于同个的连通块的格子标记相同的数比如，和，都表示第，个格子属于个连通块，第，个格子属于个连通块为了避免出现同个连通信息有不同的表示，般会使用最小表示法种最小表示法为所有的障碍格子标记为，第个非障碍格子以及与它连通的所有格子标记为，然后再找第个未标记的非障碍格子以及与它连通的格子标记为，„„，重复这个过程，直到所有的格子都标记完毕比如连通信息，表示为，还有种最小表示法，即个连通块内所有的格子都标记成该连通块最左边格子的列编号，比如上面这个例子，我们表从左到右，表示无插头，表示有插头括号内的数表示的是格子的列编号，个括号内的格子属于个连通块中国国家集训队论文长沙市雅礼中学陈丹琦第页示为，两种表示方法在转移的时候略有不同，本文后面将会提到如上图三个状态我们可以依次表示为，状态表示的优化通过观察可以发现如果轮廓线上方的个格子中个格子没有下插头，那么它就不会再与轮廓线以下的格子直接相连，它的连通性对轮廓线以下的格子不会再有影响，也就成为了冗余信息不妨将记录格子的连通性改成记录插头的连通性，如果这个插头存在，那么就标记这个插头对应的格子的连通标号，如果这个插头不存在，那么标记为这样状态就从精简为上图三个状态表示为优化后不仅状态表示更加简单，而且状态总数将会大大减少逐格递推按照从上到下，从左到右的顺序依次考虑每格分析转移完，这个格子后哪些信息对后面的决策有影响同样我们可以刻画出轮廓线，即轮廓线上方是已决策格子，下方是未决策格子由图可知与轮廓线直接相连的格子有个，直接相连的插头有个，包括个格子的下插头以及，的右插头为了保持轮廓线的连贯性，不妨从左到右依次给个格子标号，个插头标号类似地，我们需要记录与轮廓线直接相连的个插头是否存在以及个格子的连通情况通过上面的分析，很容易写出动态规划的状态，表示当前转移完，这个格子，个插头是否存在表示成个位的二进制数，以及个格子的连通性为的方案总数逐行递推的时候我们提到了状态的优化，同样地，我们也可以把格子的连通性记录在插头上，新的状态为，上图个状态依次为因为第种表示法更加直观，本文如果不作特殊说明，默认使用第种最小表示法中国国家集训队论文长沙市雅礼中学陈丹琦第页转移状态状态的转移开销主要包含两个方面每个状态转移的状态数，计算新的状态的时间逐行递推假设从第行转移到第行，我们需要枚举第行的每个格子的状态共种情况，对于任何个非障碍格子，它是否有上插头和左插头已知，因此最多只有种情况，状态的转移数枚举完第行每个格子的状态后，需要计算第行个格子之间的连通性的最小表示，通常可以使用并查集的数组对其重新标号或者重新执行次，时间复杂度为，最后将格子的连通性转移到插头的连通性上特别需要注意的是在转移的过程中，为了避免出现多个连通块，除了最后行，任何时候个连通分量内至少有个格子有下插头逐格递推仔细观察下面这个图，当转移到时，轮廓线上个格子只有，被改成个插头只有个插头被改动，即，的右插头修改成，的下插头和，的下插头修改成，的右插头转移的时候枚举，的状态分情况讨论般棋盘模型的逐格递推转移有类情况新建个连通分量，合并两个连通分量，以及保持原来的连通分量下面针对本题进行分析情况新建个连录所有至少有个顶点在轮廓线上的格子的连通和染色情况，即包括，在内的个格子个优化的方向扩展的状态中无效状态的总数很大程度上决定了算法的效率比如中如果出现右图的状态，那么无论之后如何决策，都不可能满足同色的格子互相连通的性质，因此它是个无效状态对于任何个染色棋盘问题，如果从左到右有个相互不嵌套的连通块，同色同色且与，不同色，那么这个状态为无效状态小结本章介绍了解决类棋盘染色问题的般思路无论染色规则多么复杂，我们只要在基本状态即轮廓线上方与其相连的格子的连通性以及染色情况的基础上，根据题目的需要在状态中增加对以后的决策可能产生影响的信息，问题都可以迎刃而解了四类基于非棋盘模型的问题本章将会介绍类基于非棋盘模型的连通性状态压缩动态规划问题，它虽然不具有棋盘模型的特殊结构，但是解法的核心思想又跟棋盘模型的问题有着异曲同工之处嵌套的概念可以用广义的括号匹配的表示方法来理解中国国家集训队论文长沙市雅礼中学陈丹琦第页例生成树计数问题描述给你个个点的无向连通图，其边集为任何两个不同的点，如果，那么有条无向边已知和，求这个图的生成树个数，算法分析这个题给我们的第印象是非常大，却非常小生成树最重要的两个性质无环，连通那么如果按照，的顺序依次考虑每个点与前面的哪些点相连，并且保证任何时候都不会出现环，最后统计所有的点全部在个连通分量内的方案总数即为最终的答案在棋盘模型的问题中，我们提出了轮廓线这个概念，任何时候只有轮廓线上方与其直接相连的格子对以后的决策会产生影响类似地我们分析下这个问题，当我们确定了的所有点的连边情况后，哪些信息对以后的决策会产生影响这些点与之后的点定没有边相连，那么对以后的点的决策不会产生直接的影响，因此我们需要记录的仅仅是这个点的连通