acm动态规划方案总结.doc

Pku acm 1163 the Triangle 动态规划题目总结(一)题目：对于一种有数字构成二叉树，求由叶子到根一条途径，使数字和最大，如： 73 8 8 1 02 7 4 4 4 5 2 6 5这个是典型动态规划，也是最最基本、最最简朴动态规划，典型多段图。思路就是建立一种数组，由下向上动态规划，保存页子节点到当前节点最大值，Java核心代码如下：for(int i=num-2;i=0;i-)for(int j=0;j=i;j+)/该句是整个动态规划核心numberij=Math.max(numberi+1j,numberi+1j+1)+numberij;带有详细注释代码可以在获得Pku acm 1579 Function Run Fun 动态规划题目总结(二)Consider a three-parameter recursive function w(a，b，c)：if a = 0 or b = 0 or c 20 or b 20 or c 20，then w(a，b，c) returns：w(20，20，20) if a b and b c，then w(a，b，c) returns：w(a，b，c-1) + w(a，b-1，c-1) - w(a，b-1，c) otherwise it returns：w(a-1，b，c) + w(a-1，b-1，c) + w(a-1，b，c-1) - w(a-1，b-1，c-1)这自身就是一种递归函数，要是按照函数自身写递归式，成果必定是TLE，这里我开了一种三维数组，从w(0,0,0)开始递推，逐渐产生到w(20,20,20)值，复杂度O(n3).总结：这道题是很地道DP，由于它子问题实在是太多了，因此将问题成果保存起来，刘汝佳算法艺术和信息学竞赛中115页讲到自底向上递推，这个例子就非常典型。总体来说这个题目还是非常简朴，但是这个思想是地道动态规划。带有详细注释代码可以在获得Pku acm 2081 Recamans Sequence 动态规划题目总结(三)一道很简朴动态规划，依照一种递推公式求一种序列，我选取顺序求解，即自底向上递推，一种int数组result依照前面值依此求出序列每一种成果，此外一种boolean数组flagi记录i与否已经出当前序列中，求result时候用得着，这样就避免了查找。核心java代码为：for(i=1;i0&flagresulti-1-i=false)resulti = resulti-1-i;flagresulti-1-i = true;elseresulti = resulti-1+i;flagresulti-1+i = true;带有详细注释代码可以在获得Pku acm 1953 World Cup Noise 动态规划题目总结(四)给定一种不大于45整数n，求n位2进制数中不含相邻1数个数。看似简朴一道题，如果当n=45时，对245次方检查，是无法完毕任务。先分析一下这个问题：N以1结尾个数以0结尾个数总和111221233对于n=1来说，以1结尾、以0结尾个数都是1，总和是2，下面过度到2：对于所有以1结尾数，背面都可以加上0，变为n=2时以0结尾，而只有结尾为0数才干加上1（由于不能有两个持续0），这样就可以在n=2格里分别填上1、2，总和算出来为3，以此类推，咱们可以算出所有n=45值，然后依照输入进行相应输出。核心代码如下：int i,num,count,array502,j=0;array11 = 1;array10 = 1;for(i=2;i50;i+)arrayi0 = arrayi-11;arrayi1 = arrayi-11+arrayi-10;咱们可以继续找出规律，其实这个就是斐波那切数列数列：FN = FN-1+FN-2;可以继续简化代码。带有详细注释代码可以在获得Pku acm 1458 Common Subsequence 动态规划题目总结(五)求两个string最大公共字串，动态规划典型问题。算法导论有详细解说。下面以题目中例子来阐明算法：两个string分别为：abcfbc和abfca。创立一种二维数组result,维数分别是两个字符串长度加一。咱们定义resultij表达Xi和Yj 最长子串(LCS).当i或j等于0时，resultij=0. LCS问题存在一下递归式：resultij = 0i=0 or j=0resultij = resulti-1j-1+1Xi= =Yjresultij = MAX(resulti-1j，resultij-1)Xi！=Yj对于以上例子，算法如下：Resultij:abcfba012345600000000a10111111b20122222f30122333c40123333a50123334从最后一种格向上顺着箭头方向可以找到最长子串构成，在有箭头构成线段中，具有斜向上箭头相应字符是其中一种lcs。Java代码核心某些如下：for(int i=0;ilength1;i+)resulti0 = 0;for(int i=0;ilength2;i+)result0i = 0;for(int i=1;i=length1;i+)for(int j=1;jresultij-1?resulti-1j:resultij-1;System.out.println(resultlength1length2);带有详细注释代码可以在获得Pku acm 2250 Compromise 动态规划题目总结(六)这个也是求最长公共字串，只是相比Common Subsequence需要记录最长公共字串构成，此时箭头标记就用上了,在程序中，用opt存储标记，0表达朝向左上方，1表达指向上，-1表达指向左。result存储当前最大字串长度。在求最优解时，顺着箭头从后向前寻找公共字串序号，记录下来，输出即可。该算法在算法导论中有详细解说。带有详细注释代码可以在获得。Pku acm 1159 Palindrome 动态规划题目总结(七)给一种字符串，求这个字符串至少增长几种字符能变成回文，如Ab3bd可以增长2个字符变为回文：Adb3bdA。通过这样结论可以和最长公共子串联系起来(未证明)：S和S (注:S是S反串)最长公共子串其实一定是回文。这样咱们就可以借助lcs来解决该题，即用s长度减去lcs值即可。核心Java代码为：total-LCS(string,new StringBuffer(string).reverse().toString();/函数LCS返回两个stringlcs长度带有详细注释代码可以在获得Pku acm 1080 Humman Gene Function 动态规划题目总结(八)这是一道比较典型DP，两串基因序列包括A、C、G、T，每两个字母间匹配都会产生一种相似值，求基因序列（字符串）匹配最大值。这题有点像求最长公共子序列。只但是把求最大长度改成了求最大匹配值。用二维数组optij记录字符串a中前i个字符与字符串b中前j个字符匹配所产生最大值。如果已知AG和GT最大匹配值，AGT和GT最大匹配值，AG和GTT最大匹配值，求AGT和GTT最大匹配值，这个值是AG和GT最大匹配值加上T 和T匹配值，AGT和GT最大匹配值加上T 和-匹配值，AG和GTT最大匹配值加上-和T匹配值中最大值，因此状态转移方程：optij = max(opti-1j-1+table(bi-1,aj-1),optij-1+table(-,aj-1),opti-1j+table(-,bi-1);NullAGTGATGNull-3-5-6-8-11-12-14G-2T-3T-4A-7G-9第0行，第0列表达null和字符串匹配状况，成果是-和各个字符累加：for(i=1;i=num1;i+)opt0i = opt0i-1+table(-,ai-1);for(i=1;i=num2;i+)opti0 = opti-10+table(-,bi-1);optnum2num1即为所求成果。带有详细注释代码可以在获得Pku acm 2192 Zipper 动态规划题目总结(九)这个题目规定判断2个字符串能否构成1个字符串，例如cat和tree能构成tcraete。咱们定义一种布尔类型二维数组 array,arrayij表达str1i和str2j能否构成stri+j.i=0或者j=0表达空字符串，因此初始化时，array0j表达str1前j个字符与否和str都匹配。对于str=tcraete:NullcatNull1000t1r0e0e0可以证明：当arrayi-1j( arrayij上面一格)和arrayij-1( arrayij左面一格)都为0时，arrayij为0.当arrayi-1j( arrayij上面一格)为1且左面字母为stri+j时或者当arrayij-1( arrayij左面一格)为1且上面字母为stri+j时，arrayij为1.这就是状态转移方程为。核心Java代码：if(arrayij-1&str1.charAt(j-1)=str.charAt(i+j-1)|arrayi-1j&str2.charAt(i-1)=str.charAt(i+j-1)arrayij = true;elsearrayij = false;带有详细注释代码可以在获得Pku acm 3356 AGTC 动态规划题目总结(十)一种字符串可以插入、删除、变化到另一种字符串，求变化最小环节。和最长公共子序列类似，用二维数组optij记录字符串a中前i个字符到字符串b中前j个字符匹配所需要最小步数。如果已知AG到GT最小步数，AGT到GT最小步数，AG到GTT最小步数，求AGT到GTT最小步数，此时T= =T，这个值是AG到GT最小步数，AGT到GT最小步数加一(AGT到GT最小步数等于AGTT到GTT最小步数，加一是将T删除一步)，AG到GTT最小步数加一(AG到GTT最小步数等于AGT到GTTT最小步数，加一是在AGT上增长T一步)。如果已知AG到GT最小步数，AGA到GT最小步数，AG到GTT最小步数，求AGA到GTT最小步数，此时A！=T，这个值是AG到GT最小步数加一(A变化为T)，AGA到GT最小步数加一(AGA到GT最小步数等于AGAT到GTT最小步数，加一是将T删除一步)，AG到GTT最小步数加一(AG到GTT最小步数等于AGA到GTTA最小步数，加一是在GTTA上删除A一步)。因此状态转移方程：if(str1.charAt(i-1)=str2.charAt(j-1)arrayij = Math.min(Math.min(arrayi-1j-1，arrayi-1j+1)，arrayij-1+1);elsearrayij = Math.min(Math.min(arrayi-1j-1+1，arrayi-1j+1)，arrayij-1+1);初始化时候和最长公共子序列不同，由于第0行，第0列表达null转化到字符串状况，成果是字符串长度：for(int i=0;i=m;i+)arrayi0 = i;for(int i=0;i num_arrayi且max_arrayj= max_arrayi,那么max_arrayj就要加1，因此递推公式为：if(num_arrayi=num_arrayj&max_arrayi=max_arrayj)max_arrayi+;最后选最大一种max_arrayi就是最长下降子序列个数。Java核心某些代码：for(int i=1;ilength;i+)for(int j=0;ji;j+)if(num_arrayi=num_arrayj&max_arrayimax_value)?max_arrayi:max_value;max_value是最后成果。带有详细注释代码可以在获得Pku acm 2533 Longest Ordered Subsequence 动态规划题目总结(十二)这个题目和1887 Testing the CATCHER一模同样，没有什么值得说，核心c代码如下：for(i=1;i=n;i+)for(j=1;ji;j+)if(maxinumj)maxi+;if(maxiresult)result=maxi;printf(%dn,result);带有详细注释代码可以在获得Pku acm 1631 Bridging signals 动态规划题目总结(十三)这个题目可以转化为最长上升子序列，这样这个题目似乎就和2533 Longest Ordered Subsequence 1887 Testing the CATCHER同样了，迅速写下代码，成果超时！看来只能用O(nlogn)算法了。在O(n2)算法中：创立一种一维数组arrayj，opt,arrayj表达序列元素，opti表达以第i个元素结尾序列中最长下降子序列，初始化为1，对于一种opti，遍历前面每个元素j，如果arrayjarrayi且optj=opti,那么optj就要加1，在这里，遍历前面每个元素j，寻找此前最大子序列时间复杂度为O(n)，如果咱们在一种有序序列中查找此前最大序列长度，咱们就可以用二分查找，时间复杂度就会降为O(logn),总时间复杂度就会为O(nlogn)。为此，咱们增长一种一维数组B，Bi表达当前序列为i末尾元素最小值。 例如对于序列：4 2 6 3 1 5 ：i123456array426315opt112213B135构建过程如下：i=1时，opti=1 Bi=4(当前为1序列末尾元素最小值)opt111111B4i=2时，2不不不大于4，因此opti=1,将B1更新为2opt111111B2i=3时，6不不大于2，因此opti=1+1,将B2更新为6opt112111B26i=4时，3在2 6之间，因此opti=1+1,将B2更新为3opt112211B23i=5时，1不大于2，因此opti=1,将B1更新为1opt112211B13i=6时，5不不大于3，因此opti=2+1,将B3更新为5opt112213B135opt6就是最后成果。从构建过程可以容易证明一下两点：B是递增。B是当前序列为i末尾元素最小值。以上“2不不不大于4”，“3在2 6之间”等等判断采用二分查找，因此总时间复杂度为：O(nlogn)，核心c代码如下：for(i=1;i=n;i+) num = arrayi; left = 1; right = Blen; while(left=right) mid = (left+right)/2; if(Bmidnum) left = mid+1; else right = mid-1; opti = left; Bleft = num; if(Blenleft) Blen = left;if(max=j,遍历i-1行前j列,求出当前最大值。Opt123451723-5-24162-15021+7-4+max(7,23,-5)10+max(7,23,-5,-24)23+max()3-150-150-150-150-150I=3:Opt123451723-5-24162-150281933463-150-150-4+max(-150,28)-20+max()20+max(-150,28,19,33)最后取第i行最大值即可，核心c代码：for(i=2;i=r;i+)for(j=1;j=i)for(k=1;kj;k+)if(optijopti-1k+originij)optij=opti-1k+originij;带有详细注释代码可以在获得Pku acm 1088 滑雪 动态规划题目总结(十五)1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一种人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面例子中，一条可滑行滑坡为24-17-16-1。固然25-24-23-.-3-2-1更长。事实上，这是最长一条。输出最长区域长度。Optij表达位置i j上最大下降距离，如果其周边4个点存在高度比i j高，且opt没有ij 大点，则optij=opt周边+1；此外，这个问题中存在大量重复问题，应当将计算成果存储起来，避免重复计算。核心某些c代码为：for(k=0;k4;k+)if(isIn(i+dxk,j+dyk) & heigthijheigthi+dxkj+dyk)int num = dp(i+dxk,j+dyk);if(optij0 temp i+1= tempi+ai(继续在前一种子段上加上ai),否则tempi+1=ai(不加上前面子段)，也就是说 状态转移方程：tempi = (tempi-10?tempi-1:0)+bufi;对于刚才例子 temp： 9 11 -5 2，然后取temp中最大就是一维序列最大子段。求一维最大子段和函数：int getMax(int buf100,int n)int temp101,max=n*(-127);memset(temp,0,4*(n+1);for(int i=1;i0?tempi-1:0)+bufi;if(maxtempi)max=tempi;return max;下面扩展到二维状况：考察下面题目中例子：0 -2 -7 09 2 -6 2-4 1 -4 7-1 8 0 -2咱们分别用i j表达起始行和终结行，遍历所有也许：for(i=1;i=n;i+)for(j=i;j=n;j+) 咱们考察其中一种状况 i=2 j=4，这样就相称与选中了2 3 4三行，求那几列组合能获得最大值，由于总是 2 3 4行，因此咱们可以将这3行”捆绑”起来，变为求 4(9-4-1),11(8+2+1),-10(-6-4+0),7(7+2-2)最大子段和，ok，问题成功转化为一维状况！带有详细注释代码可以在获得Pku acm 1014 Dividing 动态规划题目总结(十七)刚AC了，趁热打铁，写下解题报告，这道题很早就在joj上做过，当时不懂得dp，只会用很菜办法，成果虽然joj这道题仅规定10s还是会超时！思想：本题是找按价值均分大理石方案与否存在，由于分派时不能破坏大理石，因此有个显而易见剪枝：当所有大理石总价值为奇数时必定不能被均分。把问题转化一下即：由一种人能否从原大理石堆中取出总价值为本来一半大理石,本题重要算法是动态规划,数组flag代表状态,设总价值为sum.当flagk=true时，阐明，可以有一人获得价值k,此外一人获得价值V-k大理石分派方案。反之若flagk=false阐明这种分派方案不存在.咱们任务就是计算出flagsum/2是true还是false，显然有flag0=true方案存在，即一种人什么都不分，此外一种人拿走所有大理石.设i（16）为石头价值，试想若flagk=true，如果能再向k中增长一价值为i大理石，则flagk+i=true必然成立.石头有两个属性，一种是价值另一种是数量，这里arrayi代表价值为i大理石数量，咱们依照其中一种属性：价值来划分阶段。即for(inti=1;i=0;j-)/从当前最大值flag开始，依照前面提到flagj=true成立则flagj+i=true亦成立理论，在原有状态flagj=true已存在条件下加入stonei阶段石头,得到新状态还是举个例子吧：3 0 1 2 0 0flag :sum/2=6i0123456flag :1000000对于i=1 array1 = 3 由于flag0 = true,因此flag1，flag2，flag3都变为true：i0123456flag :1111000对于i=2 array2 = 0 不考察对于i=3 array3 = 1 由于flag0 flag1，flag2，flag3= true,因此flag3，flag4，flag5，flag6都变为true：i0123456flag :1111111等等等等，咱们任务是判断flagsum/2与否为真。这样程序基本框架就有了：dp函数如下：bool dp(int array7) bool flag60001; int i,j,k,sum = 0,max=0; for(i=1;i=6;i+) sum += arrayi*i; if(sum%2!=0) return false; memset(flag,0,sizeof(flag); flag0 = true; for(i=1;i0) for(j=max;j=0;j-) /至于为什么要从大到小，写成从小到大，调试一下就可以看出问题，/例如有1个1，本来flag0 = true,循环一遍后flag1 = true,此时再判断flag1=true,继续flag2 = true就不/合题意了，从大到小可以解决这个问题 if(flagj) for(k=1;k=arrayi;k+) if(j+k*i=sum/2) return true; else if(j+k*imax) max = j+k*i; if(j+k*isum/2) max = sum/2; flagj+k*i = true; return false;这样问题就解决了，submit，成果超时，从joj上试了一下，成果ac，6s多，距离poj1s还很远。咱们考察如果flagj+k*i已经等于true，就不用继续循环下一种k了，直接break就可以了，详细因素是这样：假设当前flag序列是这样：1 1 0 1 1 0 1 1 0 1，当前考察是 i=3；arrayi=5，就是要在这个基本上加上5个3，按照程序意思，从最后一种1开始依此加上3，将其值变为1，一共加上5个，然后在倒数第二个1上依此加上3，将其值变为1，一共加上5个，这个过程不会碰见flag=1状况，给倒数第三个1依此加3时候，会遇到：flag=1,这个时候就可以break了，由于这时候还需要加4个3都在最后一种1加5个3时候加过了，这里要注意是，给每个1加上3时候，只会遇到”旧”flag=1,不会遇到新增长flag=1,而旧1已经加过了arrayi个i，因此就不用加了，直接退出就行了。修改后裔码： for(i=1;i0) for(j=max;j=0;j-) if(flagj) for(k=1;ksum/2|flagj+k*i) break; flagj+k*i = true; max += arrayi*i; if(maxsum/2) max = sum/2;这样就ac了。0ms。带有详细注释代码可以在获得Pku acm 1160 post office 动态规划题目总结(十八)题目给出m个村庄及其距离，给出n个邮局，规定怎么建n个邮局使代价最小。思路：用optij记录把前i个邮局建到前j个村庄中最优解，用costij记录所有在i到j村庄中，建1个邮局最小代价。显然邮局应当设到中点。让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k=n)，则状态转移方程为opti+1j+k=minoptij+costj+1j+k; (k+j=n)Cost数组存储从i到j中有一种邮局最小代价，显然该邮局应当放在中间，构造cost代码和成果如下：f