一类典型的动态规划问题解析长沙市雅礼中学朱全民(难待学习)

1、一类典型动态规划问题解析1Censored! 给定N个单词，M个字符。现在问你在长度为len的所有可能句子中。不出现给定的任何一个单词有多少种可能。(n=10,m=50,len=50)2一道简单问题问题描述:用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。用容斥原理解决!3分析 出现dog字样的排列，相当于把dog作为一个单元参加排列，故类似有： 由于god,dog不可能在一个排列中同 时出现，故： 类似：4 由于gum,dog可以在dogum字样中同时出现，故有： 类似有god和depth可以在godepth字样

2、中同时出现，故 god和thing可以在thingod字样中同时出现，从而 分析5分析6分析 由于god、depth、thing不可以同时出现，故有： 其余多于3个集合的交集都为空集。 故满足要求的排列数为：7分析时间复杂度容斥原理需要求任意两个集合,三个集合的交集对于n个单词,时间复杂度为O(2n)。对于任意两个单词,需要判断两个单词是否有相同部分.这需要用模式匹配的算法来进行分析,时间复杂度跟单词的长度成正比。容斥原理的计算,需要用高精度乘法。因此,整的时间复杂度为O(单词总长度 * 2n *高精度)。n=10,m=50,len=50,这个时间复杂度有点大!8回到原题举例分析3个字符QWE

3、不能出现QQ,Q,WEE。长度为3的句子一共有7个,WEW,EWW,EWE,EEW,EEE9考虑下面这样一颗单词树每个点实际上表示了一个单词。也就是从根节点走到这个点路上的字符加起来。如右图的3个叶子节点。设Ci表示第i个点代表的字符。由于每个节点连出去的边可能没有M条，那么我们把缺少的边都补成虚边。设C=Ci+虚边上的字符.由于不存在Cj=C。那么虚边指向的节点就是在C中出现的最长后缀。10分析如右图，我们补充了一个ab节点的虚边设Fi,j表示用了i个字符走到了j这个节点。考虑Fi,j的意义？Fi,j意味着这i个字符组成的串出现在单词树中的最长后缀为Cj。11样例分析12这样我们很容易写出状

4、态转移方程Fi,j=Fi-1,k(j不是叶子节点,k通过某条实边或虚边能到达j)边界为F0,0=1(0为根节点)答案就是Flen,i(i非叶子节点)时间复杂度O(len*(节点总数)*m*高精度)=O(50*500*50*20)=O(25*106)13Blocks Jimmy最近迷上了一款叫做方块消除的游戏. 游戏规则如下：n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域). 游戏时，你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x2的分值.方块消去之后，右边的方格将向左移动.虽然游戏很简单，但是要得到高分也不是很容易.J

5、immy希望你帮助他找出最高可以得到多少分N200.14Sample如图，依次消去灰,白,黑区域，你将得到42+32+22=29分，这是最高得分.15算法分析合并颜色序列，如 1 1 1 3 3 2 4 4 4 5 5 根据方块消除的规则，连在一起的相同颜色方块可以合并。 上面的颜色序列为(1,3),(3,2),(2,1),(4,3),(5,2),其中(a,b)表示有b个颜色为a的连在一起.于是题目可以表示成colori,leni,1=i=m, m表示颜色序列总共有m段. 上面的颜色序列中, m = 5, color1 . 5=(1,3,2,4,5)len 1 . 5=(3,2,1,3,2)1

6、6定义状态设S(i,j,k)为(colori,leni),(colori+1,leni+1) (colorj-1,lenj-1)的连续同色整段以及在一系列消除操作后j后接了k个颜色为colorj的方块(colorj,lenj+k)的一个颜色序列.设f(i,j,k)表示消除S(i,j,k)这一个颜色序列可以得到的最大分值.算法分析17算法分析动态规划转移如果立刻将(colorj,lenj+k)这一段消除，则转移为f(i,j-1,0)+(lenj+k)2如果lenj+k暂时不消除而连接到上一个颜色相同的块上,则转移为f(i,p,k+lenj)+f(p+1,j-1,0). 其中colorp=colo

7、rj, i=pj18动态规划转移方程 f(i,j,k)=Maxf(i,j-1,0)+(lenj+k)2, f(i,p,k+lenj)+f(p+1,j-1,0)算法分析初值 f(i,i-1,0)=0答案 f(1,m,0)时间复杂度 O(n4)空间复杂度 O(n3)19注意细节1. 计算Restj表示第j块后面有多少个颜色 为colorj的方块，以确定k的范围.2. p不需要直接从i到j-2枚举，因为要求 colorpcolorj.计算Prevj表示j之前最 后一个与j同色的块. 计算就可以顺着j找到p=prevj, p=prevp 直到pi为止.20Robots 在一个n*m的棋盘内，一些格子里

8、有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。数据范围:n=100,m=10021举例最多能拾5块。有4种方法。22分析因为只能向右或者向下走。也就是说不能走回头路。于是考虑动态规划。设Fi,j表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。Gi,j表示在fi,j最大的时候，有多少种方案。Ci,j=1表示(i,j)点有垃圾。Ci,j=0表示没有。23状态转移方程根据(i,j)只能从(i-1,j)或者(i,j-1)走过来。于是fi

9、,j=Maxfi-1,j,fi,j-1+ci,j.gi,j=gi-1,j*k+gi,j-1*L。如果fi-1,j+ci,j=fi,j，则K=1否则K=0。如果fi,j-1+ci,j=fi,j，则L=1否则L=0。24总结于是我们得到第1，2问的答案。对于第3问，我们只要简单得在动态规划的时候记录一个决策即从哪个方向走过来的就可以了。时间复杂度O(nm)。25附加问题1怎样使得最少的机器人捡完所有的垃圾？在这个图中，我们只需要2个机器人就能捡完所有的垃圾。26考虑这些机器人组成的路径假设1号机器人组成的路径是A11,A12,A13.2号机器人的路径是A21,A22,A23(Aij代表一个垃圾的位

10、置)假设看成A12和A11配对，A13和A12配对，A22和A21配对，A23和A22配对的话那么N个点一组配对就对应了一组机器人和他们的路径。27继续分析考虑每一个机器人的路径中只有起始点Ai1 这1个点没有配对的点，也就是说在N个点的一次配对中，有多少个没有配对的点，也就有多少组路径。配对？配对最多的点？这让我们想起了二分图的最大匹配。28于是我们的算法流程这样的：1.构造2分图：如果一个垃圾点X能向右或者向下走能到达垃圾点Y。则连一条X-Y的边。2.求最大匹配T。3.所有的垃圾站tot-|T|就是我们要求得答案。 方案按照上文所说，路径上每一个点I紧跟在二分图中i所匹配的点j后面即可。2

11、9总结巧妙的转化关系是这道题目的关键。时间复杂度:O(最大匹配的时间复杂度)=O(tot3)tot为垃圾点的个数。30附加问题2假设要让K个机器人捡完所有的垃圾。如何使得捡垃圾最多的人最少。31分析K=2或者k=3的时候，可以考虑使用动态规划。Fx1,x2.xk,y1,y2.yk表示当前这k个人为于x1.xk这3个位置，且x1.xk左上没有垃圾了。这k个人分别捡了y1.yk个垃圾。K更大的时候，可以考虑采用搜索+剪枝。因为问题的方案很多。所以有比较好的效果。32Hotel 有N个男人，M个女人，其中有C对夫妇要住房。现在有P个房子。每个房子有个费用Ci和床位Bi。住房有以下要求:1.每个房子住

12、的人数不能超过Bi2.一个房间住了夫妇，不能再住其他人。3.不考虑夫妇情况下：一个房间住了男人后，不能再住女人。对女人也是一样。问最少的费用。(n500,m500,P500,Bisize,lsize) ，那么肯定无论如何Ci/Bi最小的那些房间肯定会被选到。于是我们可以贪心在ksize,lsize的时候，给他们安排Ci/Bi最小的房间。然后再进行动态规划。由于Bi=5.所以size=20就够了。这样时间复杂度就很低了。36Distributing tasks 给你一个2*n的矩阵。每个方格内有一个任务难度为Ci,j。现在你有M个人。每个人将会完成一定量的任务：这个任务或是在矩阵内一段1*k内的

13、任务或是矩阵内一段2*k的任务。每个人的任务量就是完成任务的难度和。要求每个人的任务不重复，且矩阵内的所有任务都要完成。现在问你任务量最多的那个人至少要完成多少。n10001, m=min2*n,1000. 37举例分析如下图所是，红，黄，绿分别代表3个人。每个人的任务量都是6。38分析对于这类要求最大的最小问题，我们还是首选二分答案。假设当前每局的答案T。也就是说每个人的任务量上限都为T。我们只要判断能否把2*n的矩阵割成L块(L=m)使得每块任务量=T。39考虑动态规划设Fi表示第1列到第i列被切割完后，使用的最少人数。如果第i列是被一个2*k的矩阵覆盖了。那么我们维护一个指针就可以在均摊O(n)内算出所有的这种情况Fi=Minfi,fj+140考虑是被一些1*k的矩阵覆盖由于这个时候2行之间没有关系，那么我们当然从后往前考虑每一段，现在每一段能做的任务越多越好。这样我们得出了一个有效的算法。维护2个指针P,Q。一开始位置都在i。每次找到P,Q