acm动态规划总结.doc

Pku acm 1163 the Triangle 动态规划题目总结(一)题目：http:/acm.pku.edu.cn/JudgeOnline/problem?id=1163对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如： 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;带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1579 Function Run Fun 动态规划题目总结(二)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1579Consider 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页讲到自底向上的递推，这个例子就非常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 2081 Recamans Sequence 动态规划题目总结(三)http:/acm.pku.edu.cn/JudgeOnline/problem?id=2081一道很简单的动态规划，根据一个递推公式求一个序列，我选择顺序的求解，即自底向上的递推，一个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;带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1953 World Cup Noise 动态规划题目总结(四)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1953给定一个小于45的整数n，求n位2进制数中不含相邻1的数的个数。看似简单的一道题，如果当n=45时，对2的45次方检查，是无法完成的任务。先分析一下这个问题：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;可以继续简化代码。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1458 Common Subsequence 动态规划题目总结(五)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1958求两个string的最大公共字串，动态规划的经典问题。算法导论有详细的讲解。下面以题目中的例子来说明算法：两个string分别为：abcfbc和abfca。创建一个二维数组result,维数分别是两个字符串长度加一。我们定义resultij表示Xi和Yj 的最长子串(LCS).当i或j等于0时，resultij=0. LCS问题存在一下递归式：resultij = 0 i=0 or j=0resultij = resulti-1j-1 Xi= =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);带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 2250 Compromise 动态规划题目总结(六)http:/acm.pku.edu.cn/JudgeOnline/problem?id=2250这个也是求最长公共字串，只是相比Common Subsequence需要记录最长公共字串的构成，此时箭头的标记就用上了,在程序中，用opt存放标记，0表示朝向左上方，1表示指向上，-1表示指向左。result存放当前最大字串长度。在求最优解时，顺着箭头从后向前寻找公共字串的序号，记录下来，输出即可。该算法在算法导论中有详细的讲解。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得。Pku acm 1159 Palindrome 动态规划题目总结(七)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1159给一个字符串，求这个字符串最少增加几个字符能变成回文，如Ab3bd可以增加2个字符变为回文：Adb3bdA。通过这样的结论可以和最长公共子串联系起来(未证明)：S和S (注:S是S的反串)的最长公共子串其实一定是回文的。这样我们就可以借助lcs来解决该题，即用s的长度减去lcs的值即可。核心的Java代码为：total-LCS(string,new StringBuffer(string).reverse().toString();/函数LCS返回两个string的lcs的长度带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1080 Humman Gene Function 动态规划题目总结(八)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1080这是一道比较经典的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即为所求结果。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 2192 Zipper 动态规划题目总结(九)http:/acm.pku.edu.cn/JudgeOnline/problem?id=2192这个题目要求判断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;带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 3356 AGTC 动态规划题目总结(十)http:/acm.pku.edu.cn/JudgeOnline/problem?id=3356一个字符串可以插入、删除、改变到另一个字符串，求改变的最小步骤。和最长公共子序列类似，用二维数组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是最后的结果。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 2533 Longest Ordered Subsequence 动态规划题目总结(十二)http:/acm.pku.edu.cn/JudgeOnline/problem?id=2533这个题目和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);带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1631 Bridging signals 动态规划题目总结(十三)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1631这个题目可以转化为最长上升子序列，这样这个题目似乎就和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;带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1088 滑雪 动态规划题目总结(十五)http:/acm.pku.edu.cn/JudgeOnline/problem?id=10881 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，问题成功转化为一维的情况！带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1014 Dividing 动态规划题目总结(十七)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1014刚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多，距离poj的1s还很远。我们考察如果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。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1160 post office 动态规划题目总结(十八)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1160题目给出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的代码和结果如下：for(i=1;i=m;i+)for(j=i;j=m;j+)costij = 0;mid = (i+j)/2;for(k=i;k=0 ?distancemid-distancek:distancek-distancemid;Costij1234567891010126101621377411720148111631681093034711266110240137205594502417508960213467470113361802228906100Optij 表示前i个邮局覆盖前j个村庄的最小代价，对于i=1来说，optij = costij,让前2个邮局覆盖前j个村庄，也就是i=2的情况，可能是一下情况的最优解：第一个邮局覆盖第一个村庄，第二个村庄覆盖2-j个村庄，或者第一个邮局覆盖第1-2个村庄，第二个村庄覆盖3-j个村庄，第一个邮局覆盖第1-3个村庄，第二个村庄覆盖4-j个村庄，等等等等。该部分的代码如下：for(i=0;i=n;i+)for(j=0;j=m;j+)if(optij3000000)for(k=1;j+koptij+costj+1j+k)opti+1j+k = optij+costj+1j+k;Optij0123456789100010126101621377411720148-511-816-1231-2768-62109-103345带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1125 Stockbroker Grapevine 动态规划题目总结(十九)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1125有向图中每一对顶点间的最短路径问题，典型的弗洛伊德算法。问题描述：已知一个含有n个顶点的各边权值均大于0的带权有向图，对每对顶点vi！=vj，要求求出每一对顶点之间的最短路径和最短路径长度。 解决方案：弗洛伊德(floyd)算法321对于这样一个例子： 4 2 2 5 2 6A0ij=costij:A0123A1123104510452206220min(6,2+5)322032min(2,2+4)0A2123A3123104min(5,4+6)10min(4,5+2)522062min(2,6+2)063min(2,2+2)203220核心的c代码如下：for(int k=1;k=n;k+) /生成A0,A1,A2.的循环for(int i=1;i=n;i+) /行for(int j=1;j=n;j+) /列/如果是i=k|j=k|i=j就保持不变，否则取最小值arrayij=(i=k|j=k|i=j)?arrayij:(arrayij(arrayik+arraykj)?arrayij:(arrayik+arraykj);最后根据题意，取每行最大值中的最小值即可。带有详细注释的代码可以在http:/download.csdn.net/user/china8848/获得Pku acm 1179 Polygon 动态规划题目总结(二十)http:/acm.pku.edu.cn/JudgeOnline/problem?id=1179多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。分析： 在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为vi，opi+1，vi+j-1。 如果这条链的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链分割为2个子链p(i，s)和p(i+s，j-s)。 设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。 这道题收获非常多：1.已经定义了变量max，然后调用一个已经定义的函数max时报