朱全民状态压缩类型动态规划.ppt

* * * * 状态压缩类型动态规划 长沙市雅礼中学 朱全民 广场铺砖问题 给出一个W行H列的广场 用1*2小砖铺盖，小砖之间互相不能重叠 问有多少种不同的铺法？ 1=W，H=11 分析 该题给出的广场的面积很小，给出了一种1*2的砖，问用砖去铺广场有多少种铺法？ 因为w,h=11,很容易想到采用有哪些信誉好的足球投注网站的方法，可以采用深搜或宽搜均可。 尽管w,h=11，不很大，但是用1*2的砖铺，深度最大可达到11，这样，如果采用深搜，对于每一层都需要回溯，时间复杂度也很高。 如果采用宽搜，每一个点都有2种铺法，因此可以扩展出2个结点，要求所有的解，必须扩展全部树结构，如果11层结点，是个完全二叉树，结点数量可达211*11 =2121 ，无论空间和时间都难以承受。 因此我们需要采用其他方法。 进一步分析 性质1：如果w和h都是奇数，则无解，否则有解。 证明：w,h都是奇数，则w*h也是奇数，由于1×2的砖有2块，因此无论铺多少块都是偶数，因此不能覆盖所有的地板。如果地板的面积S是偶数，肯定能被2整除，因此可以用S/2块砖铺满整个地板。 性质2：对于每铺一次地板，只会影响所铺的上下两行。 证明：因为是1×2的砖铺，性质显然。 性质3：如果按行铺地板，每一行的铺法都类似。 证明：显然！ 一个示例 一个6×9的面积铺法如下图: 可以看出，在按行铺的过程中，某些砖会分成两半，如图2，但最多也是向下突出一格，在图3中，我们将图2的空隙填满，则又转移到了下一种状态。 状态的表示 如果我们把行进行动态规划，则第i行的各种情况即表示第i个阶段的的各种状态。 若某格被铺了砖，则用1表示，没有铺砖，则用0表示，那么行的状态就是一个w个格子的0,1串，即w位的二进制数。如下图状态为：100100 下面就是由某个二进制数能转化到另一个二进制数的问题了。如下图,状态由100100 ? 111100 和110100 ： 动态规划 显然，对于每一行,宽度为w,每格可放0和1，因此有2w 种状态，如下图： 设f(i,s)表示铺到第i行，状态为s的方案数，则 初始值f(1,0)=1 Ans=f[h+1][0] 时间复杂度为O(h*2W) 基本位操作 若当前状态为s,对s 有下列操作： 判断第i位是否为0 ? (S 1 i) == 0，意思是将1左移i位与s进行与运算后，看结果是否为0. 将第i位置1 ? S | 1 i，意思是将1左移动i位与s进行或运算. 将第i位置0 ? S ~(1 i)，意思是s与第i位为0，其余位为1的数进行与运算。 例如：s=1010101，i=5 (S 1 i): 1010101 0100000 = 0 S | 1 i: 1010101 | 0100000 = 1110101 S ~(1 i): 1010101 1011111 = 1010101 放置操作 对于每一行有w个位置，所以每一行都有0～2w-1种状态。 对于当前行的状态s，它是由前一行的状态s’转化过来的，显然，对于该行某个位置j： 如果前一行该位置为0,那么该位置可以竖放 即 0- 1 如果前一行连续两个位置为0,那么这两个连续位置可以横放 即00- 00 如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0 ，即1- 0 W=4，h=2的求解过程 void dfs(int i, int s1, int s2, int d) { if (s == m) //如第i行已经做完，则累加 f[i + 1][s2] += f[i][s1]; else if ((jj (1 d)) == 0) //第d位为0 { dfs(i,s1, s2| (1 d), d + 1); //将第d位变为1，并右移1位 //如果第d+1位也为0，则直接有哪些信誉好的足球投注网站d+2位 if (s2 m - 1 (jj (1 (d + 1))) == 0) dfs(i,s1, s2, d + 2); } else dfs(i, s1,s2 ~(1 d), d + 1); //将第d位变为0,并右移1位 } 硬木地板 有一M×N 的矩形地板 可以使用的地板砖形状有两种： 1) 2×1的矩形砖 2) 2×2中去掉一个1×1的角形砖 你需要计算用这些砖铺满地板共有多少种不同的方案。 必须盖满，地板砖数量足够多，不能存在同时被多个板砖覆盖的部分。 1=M=9, 1=N=9 分析样例 ２×３的地板所有铺法共５种，如下图。 可以看出这题与动归４的“广场铺砖问题”完全类似。只不