最新状态压缩类型动态规划ppt课件.ppt

《最新状态压缩类型动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、广场铺砖问题给出一个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，无论空间和时间都难以承受。因此我

2、们需要采用其他方法。进一步分析性质1：如果w和h都是奇数，则无解，否则有解。证明：w,h都是奇数，则w*h也是奇数，由于1×2的砖有2块，因此无论铺多少块都是偶数，因此不能覆盖所有的地板。如果地板的面积S是偶数，肯定能被2整除，因此可以用S/2块砖铺满整个地板。性质2：对于每铺一次地板，只会影响所铺的上下两行。证明：因为是1×2的砖铺，性质显然。性质3：如果按行铺地板，每一行的铺法都类似。证明：显然！一个示例一个6×9的面积铺法如下图:可以看出，在按行铺的过程中，某些砖会分成两半，如图2，但最多也是向下突出一格，在图3中，我们将图2的空隙填满，则又转移到了下一种状态。状态的表示如

3、果我们把行进行动态规划，则第i行的各种情况即表示第i个阶段的的各种状态。若某格被铺了砖，则用1表示，没有铺砖，则用0表示，那么行的状态就是一个w个格子的0,1串，即w位的二进制数。如下图状态为：100100下面就是由某个二进制数能转化到另一个二进制数的问题了。如下图,状态由100100111100和110100：动态规划显然，对于每一行,宽度为w,每格可放0和1，因此有2w种状态，如下图：设f(i,s)表示铺到第i行，状态为s的方案数，则初始值f(1,0)=1Ans=f[h+1][0]时间复杂度为O(h*2W)基本位操作若当前状态为s,对s有下列操作：判断第i位是否为0(S&

4、1<

5、1<

6、1<

7、0100000=1110101S&~(1<

8、为0,那么该位置可以竖放即0->1如果前一行连续两个位置为0,那么这两个连续位置可以横放即00->00如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0，即1->0W=4，h=2的求解过程voiddfs(inti,ints1,ints2,intd){if(s==m)//如第i行已经做完，则累加f[i+1][s2]+=f[i][s1];elseif((jj&(1<

9、(1<

10、==0)dfs(i,s1,s2,d+2);}elsedfs(i,s1,s2&~(1<

11、，１表示已铺了砖。该题有两种类型的砖，因此对应６种铺法：对于上下两行：要能用某种类型的砖铺，必须该砖所覆盖的区域为空。a=a

12、bin(i)

13、bin(i+1);b=ba=a

14、bin(i)

15、bin(i+1);b=b

16、bin(i)a=a

17、bin(i)

18、bin(i+1);b=b

19、bin(i+1)a=a

20、bin(i);b=b

21、bin(i)a=a

22、bin(i);b=b

23、bin(i)

24、bin(i-1)a=a

25、bin(i);b=b

26、bin(i)

27、bin(i+1)#definebin(i)(1<<