提高组动态规划

提高组动态规划第1页，课件共40页，创作于2023年2月例1.ProbabilisticTranslator你要翻译一篇文章,每个原文单词都有若干候选翻译词汇.要求翻译后相邻单词的权和尽量大.例如原文是abc翻译选项为:a:xy;b:yz;c:xy权为w(y,z)=20,w(x,y)=10,w(z,x)=5则翻译成xyz权和为10+20=30原文最多50个单词.最多50个单词对权非0第2页，课件共40页，创作于2023年2月分析令f(k,t)为前k个单词的翻译结果中,其中最后一个单词采取第t种翻译,得到的最大权和第3页，课件共40页，创作于2023年2月例2.RPSChampsn(n<=500)个人进行剪刀石头布游戏,每次每人等概率的出剪刀石头或者布,直到一共只出现两种(否则重来一次,计入局数),然后分别在内部继续.两部分的局数都计入总局数.求游戏总局数的期望第4页，课件共40页，创作于2023年2月分析先计算某一局内a人出石头b人出剪刀的概率P(a,b)=(P(a-1,b)+P(a,b-1))/3则一局不重来的概率为Pn=sum{3P(i,n-i)}设fn为所求,则fn=(1-Pn)*(1+fn)+sum{3P(i,n-i)*(1+fi+fn-i)}移项得到递推公式第5页，课件共40页，创作于2023年2月例3.Collector你想收集所有硬币.最少需要取多少钱,使得不管取款机怎么给钱都可以得到所有种类硬币?例如{1,2}和{1,1}都是无解的.但{2,3}的解是5,因为只有一种方案5=2+3最多50种硬币,每个硬币面值为1到10000第6页，课件共40页，创作于2023年2月分析何时无解?存在倍数的情况?不一定.例如{3,5,8}.无解当且仅当有两种不同的方式得到所有硬币面值和sum.f(i,j)表示用前i种硬币得到j的方法总数第7页，课件共40页，创作于2023年2月例3.旅行计划某人沿高速公路旅行，白天行走，晚上在旅馆住宿，每天最多走800公里。旅行社给出了沿路旅馆的相关信息，包括离出发点的距离和该旅馆的价格.任意两个旅馆之间的距离都将在800公里以内.求出住宿费用最少的旅行计划冲突:日程最短住宿次数最少的旅行计划冲突:费用最少第8页，课件共40页，创作于2023年2月分析设d[i]为到旅馆i的最少费用，则有d[i]=min{d[j]}+cost[i]，j<i,dist(j,i)<=800算法一:直接计算,时间O(n2).如果可以快速计算一段连续区间的最小值,则时间复杂度将得到降低!算法二:用滑动窗口技术，用堆保存满足dist(j,i)<=L=800的状态d[j]，每个元素最多删除和增加一次，共O(nlogL)第9页，课件共40页，创作于2023年2月分析对窗口内的点,如果有i<j但d[i]>d[j]则可以只保留d[j],因为d[j]更好且i能取时j一定也能取在新加入结点时从右往左查找,找到位置前把结点删除,直到找到正确的位置每个点最多加入和删除一次，因此为O(n)第10页，课件共40页，创作于2023年2月例4.基因字符串变换规则A1A2A3,其中A1,A2,A3各为一个大写字母,表示字母A1可以被替换为串A2A3.给定串,判断它是否可以由字母S经过若干次替换生成.第11页，课件共40页，创作于2023年2月分析逆向思维：A[i,j,c]为真当且仅当i…j-1的子串可以合成字母c。递推时可枚举k，对于规则A1A2A3如果A[i,k,A2]且A[k,j,A3]，则A[i,j,A1]即A[i,j,A1]||=A[i,k,A2]&&A[k,j,A3]状态有26L2个，转移有262L个，总263L3。B[i,j]为i…j的子串最少可以合成几个S，O(n2)特殊处理：用整数表示c1c2能直接合成的集合e[c1,c2]，用位运算加速第12页，课件共40页，创作于2023年2月例5.n-kspecialsets我们说一个由自然数构成的集合X是n-k特殊集合，如果它满足对于集合X中的每个元素x，有1<=x<=n，集合X中所有元素的和大于k集合X中不包含任意一对相邻的自然数给出n,k，求n-k特殊集合有多少个第13页，课件共40页，创作于2023年2月分析d[i,j]为i-j特殊集的个数，则分两类不包含i的，为d[i-1,j]包含i的，为d[i-2,j-i]注意边界滚动数组第14页，课件共40页，创作于2023年2月例6.LectureHallsReservation有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。第15页，课件共40页，创作于2023年2月分析按照结束时间从小到大排序d[i]=max{d[j]}+Len[i]，其中j为右端点在i左端点前的线段集合。显然该集合是连续的若干个线段用堆维护d[j]，O(nlogn)。由于需要排序，这是下界。如果已经按右端点排序好，则需要二分找到可用线段的最右端，再插入状态第16页，课件共40页，创作于2023年2月例7.氧气瓶用(a,b,c)描述一个氧气瓶，其中a表示氧气体积，b为氮气体积，c为重量带多个氧气瓶，则三者都相加给出n种氧气瓶，选择其中的一些，使得氧气至少T升，氮气至少A升，重量最轻第17页，课件共40页，创作于2023年2月分析D[i,j,k]为只考虑前i个氧气瓶，需要氧气至少j升，氮气至少为k升的最小重量。时间复杂度：O(n*T*A)第18页，课件共40页，创作于2023年2月例8.CoolNumbers如果一个数的二进制表达式(不含前导0)中至少有三个连续0或者三个连续1,我们称它为coolnumber.例如8=(1000)2,15=(1111)2都是coolnumber,但27=(11011)2不是求a到b中的coolnumber个数.例如0到16有5个coolnumber:7,8,14,15,16;17到100有49个.0<=a<=b<=2147483647第19页，课件共40页，创作于2023年2月分析记f(x)为0到x的coolnumber个数,则答案为f(b)-f(a-1)集合分解:[0,1011010)的数分为以下几部分:0******100****1010***101100*问题转化为求已知前缀的串个数第20页，课件共40页，创作于2023年2月分析如果肯定cool了,则直接得到结果否则只需要考虑最后的连续数字.设f(i,j,k)为包含i位且最后有j个连续的k(k=0,1)时的coolnumber个数,递推即可第21页，课件共40页，创作于2023年2月例9.Code给定包含前K个字母的BST，代码为：空树(包含零个字母)的代码为空串.否则第一个字母为根，接着是左子树代码，最后是右子树代码代码排序，第n个代码记为(n,k)-代码目标：给定n,k，找到(n,K)-代码。（n,K为正整数，1<=K<=19）第22页，课件共40页，创作于2023年2月例9.Code当k=4时有14个4结点BST。它们是（按字母表顺序）：abcd，abdc，acbd，adbc，adcb，bacd，badc，cabd，cbad，dabc，dacb，dbac，dcab，dcba字母串badc是(7,4)-代码，如右图第23页，课件共40页，创作于2023年2月分析题目中讲的二叉树就是排序二叉树，而BST代码，实际上就是二叉树的先序遍历。题目中所要求的，就是把所有的有k个结点的排序二叉树排序的BST代码排序后（按字典顺序），排在第n位的代码。总数：f[i]=sum{f[j-1]*f[i-j]}计算以j为根的BST总数Xj=f[j-1]*f[k-j]，则把n与X1比较后直接可算出根。同样也可以算出左儿子和右儿子第24页，课件共40页，创作于2023年2月例10.划分把一个集合分成k份,使得它们的方差和尽量小.方差等于所有数与平均数差的平方的平均数.例如{3,4,7,10}的平均值为6,则方差为((3-6)2+(4-6)2+(7-6)2+(10-6)2)/4=7.5最多50个数,每个数为1到1000的整数例如{1000,500,1,500}分成三份,方差和最小为0.{1000},{500,500},{1}第25页，课件共40页，创作于2023年2月分析最优解一定是排序后分成若干段f(i,j)表示从i开始的数分成j段的最小方差和,则f(i,k)=min{f(j,k-1)+var(i,j)|i<j<=n},其中var(i,j)表示第i到j-1个数的方差.时间复杂度为O(n2k)第26页，课件共40页，创作于2023年2月例11.阶梯有一些高度递增的阶梯,每次可你可以如果下个阶梯比当前阶梯高1个单位,可以直接到该阶梯如果不是在第一个阶梯,都可退到前一个阶梯如果你已经连续退了K次,则可以到达比当前阶梯最多高2K个单位的任何一个阶梯用最少移动数到最后一个阶梯,或输出无解最多50个阶梯,h1=0,0<=hi<=109第27页，课件共40页，创作于2023年2月分析设f(i)为到达第i个台阶的最小次数,考虑这之前到达的最高台阶,即经过若干次后退后直接可达第i个台阶.C[0]=0;for(i=1;i<n;i++){C[i]=1000000;if(h[i]-h[i-1]==1)C[i]=C[i-1]+1;for(j=0;j<i;j++)for(k=0;k<j;k++)if((h[i]<=h[k]+P[j-k])&&(C[i]>C[j]+j-k+1))C[i]=C[j]+j-k+1;if(C[i]==1000000)return-1;}returnC[n-1];第28页，课件共40页，创作于2023年2月例12.ExtendedHappyNumbersSk(N)表示N的各位数的k次方之和.例如S2(65)=62+52=61.则N的happy值定义为不停计算Sk(N),Sk(Sk(N))…过程中得到的最小值.给定A,B,K,计算A到B的每个数的happy值之和.例如k=2时5得到的序列为5,25,29,85,89,145,42,20,4,16,37,58,89,…1<=A<=B<=106,K<=6第29页，课件共40页，创作于2023年2月分析可以到达的最大数不超过4*106,因为36+6*96=3189375<4*106用Hash判断重复,记f(n)为n的happy值,则每个f(n)最多算一次.第30页，课件共40页，创作于2023年2月例13.PrefixFreeSubsets如果一个字符串集合中没有某个串是另一个的前缀,称该集合为PrefixFree的.给一个字符串集合,统计它的子集中PrefixFree的个数.例如{“hello”,“hell”,“hi”}中除{“hello”,”hell”}和{“hello”,”hell”,”hi”}外的其他6个子集均为PrefixFree的.最多50个串,串长不超过50,串由小写字母组成第31页，课件共40页，创作于2023年2月分析算法一:建立Trie,把单词结点做标记.设f(i)为以i为根的子树中选择单词组成的PrefixFree集合的方案数,则它等于所有儿子的f值乘积.如果i本身是单词,则加1算法二:排序后i为根所在子树在序列中是连续的,且i在最前面.令d(i)为从i及其后面的单词中选出PrefixFree集合的方案总数,则d(i)=d(i+1)+d(j),其中j为第一个不以wi为前缀的单词第32页，课件共40页，创作于2023年2月例14.酸雨你是一个农夫,有一个一维农场.你有一些保护庄稼的档板.每个档板用三元组(b,e,y)表示它是一条线段(b,y)-(e,y).设所有b的最小值为B,所有e的最大值为E.买总长度尽量短的档板保护开区间(B,E)的所有庄稼.酸雨落到档板后往最近的端点流.如果落到档板中间则分成两半分别往两个端点流.有公共端点的档板相当于一块大档板最多25个档板,0<=b<e<=10,1<=y<=105第33页，课件共40页，创作于2023年2月分析F(X,Y)表示只允许买高度不超过Y的档板,挡住从集合X处下落的雨水所需要的最少档板数,则f(empty,Y)=0,且f(X,0)=infinity,对于非空集X离散化Y,时间复杂度为22E-1*maxy第34页，课件共40页，创作于2023年2月例15.植树在w*h的网格的整点里种n棵树,要求共线且相邻树的距离不小于d.下图为w=h=10,n=4,d=2时的两种方案(还有其他方案).求方案数1<=n,d<=50,1<=w,h<=500第35页，课件共40页，创作于2023年2月例16.NiceOrUgly如果一个串包含3个连续元音或者5个连续辅音,称它是ugly的,否则nice.给出包含大写字母与问号?的串,返回它是否一定为UGLY,一定为NICE或者不一定AEIOU为元音,其他为辅音H??LOWOR??是NICE的,EE?FFFF为UGLY的,HELLOW?RLD不一定(填O是nice,Z是ugly),最多50个字符第36页，课件共40页，创作于2023