最小m段和

最小m段和问题胡敏计科二班20110801208知识回顾动态规划：动态规划算法的基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。最优子结构：当一个问题的最优解包含了子问题的最优解时，称该问题具有最有子结构性质。问题描述给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？•例如：求将｛1，2，3，4，5｝分成2段的和的最大值的最小值。即n=5，m=2。•有{{1}，{2，3，4，5}}、{{1，2}，{3，4，5}}、{{1，2，3}，{4，5}}、{{1，2，3，4}，{5}}。•题目就是要对每一种分割求其m个部分和的最大值，然后在这些最大值中求出最小值。算法分析动态规划的解法：•状态转移方程：•初始值：f[0][1]=0f[i][j]表示将前i个数分成j段得到的最优值；其中j-1=k=i-1；j=i=n；1=j=m;e是保存序列的数组。f[i][j]=min{max{f[i][1]-f[k][1],f[k][j-1]}}，2=j=mf[i-1][1]+e[i]，j=1由于f[k][j-1]中k=j-1,所以k的初始值是j-1;f[i][j]=min{max{f[i][1]-f[k][1],f[k][j-1]}}，2=j=mf[i-1][1]+a[i]，j=1分析：例如将{1，2，3，4}分成3段，即m=4，n=3。第一步：①j=2，i=j，k=j-1=1，则max={max{f[1][1],2}}=2=f[2][2];②i=3,k=1,则max=max{f[1][1],5}=5;k++;k=2,max=max{f[2][1],3}=3，则min{3,5}=3=f[3][2];③i=4,k=1,max=max{f[1][1],9}=9;k++;k=2,max=max{f[2][1],7}=7,min=min{7,9}=7;k++;k=3,max=max{f[3][1],4}=6，则min=min{6,7}=6=f[4][2];第二步：①j=3,i=j,k=j-1=2,则max=max{3,f[2][2]}=3=f[3][3];②i=4,k=2则max=max{7,f[2][2]}=7;k++;k=3,则max=max{4,f[3][2]}=4;min=min{7,4}=4=f[4][3].表达式证明•f[i][j]=min{max{f[i][1]-f[k][1],f[k][j-1]}}•反证法：假设后一项不是f[k][j-1],而是将前k个数分成j-1段的其他任意一种分割下得到的最大值，不妨设为b。那么表达式则变为f[i][j]=minmax{f[i][1]-f[k][1],b}，令a=f[k][j-1]，则有ab。对于一个给定的k值，当f[i][1]-f[k][1]b时，则当前情况下的max=b，如果在其他k值情况下求得的max值都比b大，那么最后的结果f[i][j]就为b。但是由于还存在ab，正确结果应该是f[i][1]-f[k][1]和a二者之一。所以矛盾。即表达式的后一项应该是前面所得的最优值，即f[k][j-1]。正如上个例子，最后一步f[4][3]=min{max{4,f[3][2]},max{7,f[2][2]}}而f[3][2]=min{3,5}，即a=3,b=5，若f[i][j]=minmax{f[i][1]-f[k][1],b}成立，则max{4,5}=5,最后的结果f[4][3]=min{5，7}=5，不正确。代码：#includeiostream#includefstreamusingnamespacestd;intmax(intc,intd){intmax;max=(cd?c:d);returnmax;}intminmax(inta,intb,int*c){intn=a,m=b;inti,j,k,maxx,min;int**d=newint*[n+1];for(i=0;in+1;i++)d[i]=newint[m+1];d[0][1]=0;for(inte=1;e=n;e++){d[e][1]=d[e-1][1]+c[e-1];}if(m==1)returnd[n][1];for(j=2;j=m;j++)for(i=j;i=n;i++){min=10000;for(k=1;k=i-1;k++){maxx=max(d[i][1]-d[k][1],d[k][j-1]);if(maxxmin)min=maxx;}d[i][j]=min;}returnmin;}intmain(){fstreamfin(input.txt,ios::in);fstreamfout(output.txt,ios::out);inta,b;fina;finb;int*c=newint[a];for(inti=0;ia;i++)finc[i];intmin=minmax(a,b,c);for(intj=0;ja;j++)foutc[j];foutendl;fout将此a个数分成b段，结果是：;foutmin;fin.close();fout.close();return0;}