资源描述：
《一类典型的动态规划问题解析长沙市雅礼中学朱全民(难待学习).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一类典型动态规划问题解析长沙市雅礼中学朱全民Censored!给定N个单词，M个字符。现在问你在长度为len的所有可能句子中。不出现给定的任何一个单词有多少种可能。(n<=10,m<=50,len<=50)一道简单问题问题描述:用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。用容斥原理解决!!!分析出现dog字样的排列，相当于把dog作为一个单元参加排列，故类似有：由于god,dog不可能在一个排列中同时出现，故：类似：由于gum,dog可以在dogum字
2、样中同时出现，故有：类似有god和depth可以在godepth字样中同时出现，故god和thing可以在thingod字样中同时出现，从而分析分析分析由于god、depth、thing不可以同时出现，故有：其余多于3个集合的交集都为空集。故满足要求的排列数为：分析时间复杂度容斥原理需要求任意两个集合,三个集合的交集对于n个单词,时间复杂度为O(2n)。对于任意两个单词,需要判断两个单词是否有相同部分.这需要用模式匹配的算法来进行分析,时间复杂度跟单词的长度成正比。容斥原理的计算,需要用高精度乘法。因此,整的时间复杂度为O(单词总长度
3、*2n*高精度)。n<=10,m<=50,len<=50,这个时间复杂度有点大!回到原题举例分析3个字符QWE不能出现QQ,Q,WEE。长度为3的句子一共有7个WWW,WWE,WEW,EWW,EWE,EEW,EEE考虑下面这样一颗单词树每个点实际上表示了一个单词。也就是从根节点走到这个点路上的字符加起来。如右图的3个叶子节点。设Ci表示第i个点代表的字符。由于每个节点连出去的边可能没有M条，那么我们把缺少的边都补成虚边。设C’=Ci+虚边上的字符.由于不存在Cj=C’。那么虚边指向的节点就是在C’中出现的最长后缀。分析如右图，我们补充
4、了一个ab节点的虚边设F[i,j]表示用了i个字符走到了j这个节点。考虑F[i,j]的意义？F[i,j]意味着这i个字符组成的串出现在单词树中的最长后缀为Cj。样例分析这样我们很容易写出状态转移方程F[i,j]=ΣF[i-1,k](j不是叶子节点,k通过某条实边或虚边能到达j)边界为F[0,0]=1(0为根节点)答案就是ΣF[len,i](i非叶子节点)时间复杂度O(len*(节点总数)*m*高精度)=O(50*500*50*20)=O(25*106)BlocksJimmy最近迷上了一款叫做方块消除的游戏.游戏规则如下：n个带颜色方格
5、排成一列，相同颜色的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域).游戏时，你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x2的分值.方块消去之后，右边的方格将向左移动.虽然游戏很简单，但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分N<200.Sample如图，依次消去灰,白,黑区域，你将得到42+32+22=29分，这是最高得分.算法分析合并颜色序列，如11133244455根据方块消除的规则，连在一起的相同颜色方块可以合并。上面的颜色序列为(1,3),(3,2),
6、(2,1),(4,3),(5,2),其中(a,b)表示有b个颜色为a的连在一起.于是题目可以表示成color[i],len[i],1<=i<=m,m表示颜色序列总共有m段.上面的颜色序列中,m=5,color[1..5]=(1,3,2,4,5)len[1..5]=(3,2,1,3,2)定义状态设S(i,j,k)为(color[i],len[i]),(color[i+1],len[i+1])…(color[j-1],len[j-1])的连续同色整段以及在一系列消除操作后j后接了k个颜色为color[j]的方块(color[j],len[
7、j]+k)的一个颜色序列.设f(i,j,k)表示消除S(i,j,k)这一个颜色序列可以得到的最大分值.算法分析算法分析动态规划转移如果立刻将(color[j],len[j]+k)这一段消除，则转移为f(i,j-1,0)+(len[j]+k)2如果len[j]+k暂时不消除而连接到上一个颜色相同的块上,则转移为f(i,p,k+len[j])+f(p+1,j-1,0).其中color[p]=color[j],i<=p8、f(p+1,j-1,0)}算法分析初值f(i,i-1,0)=0答案f(1,m,0)时间复杂度O(n4)空间复杂度O(n3)注意细节1.计算Rest[j]表示第j块后面有多少个颜色为color[j]的方块，以确定k的范围.
