动态规划总结汇总(NOIP必备)

-1-动态规划（一）05B张婕目录一、数字添加号………………………………………………………………-2-二、乘积最大……………………………………………………………………-9-三、矩阵取数……………………………………………………………………-16-四、邮局（已修改）…………………………………………………-22-五、棋盘分割……………………………………………………………………-28-六、矩阵连乘……………………………………………………………………-35-七、能量项链……………………………………………………………………-40-八、石子合并……………………………………………………………………-45-九、加分二叉树………………………………………………………………-51-十、CUTTING（已修改）………………………………………………-56--2-1、数字添加号『题目描述』一个由数字1，2，...，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。[输入格式］从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。[输出格式］在屏幕上输出所求得的最小和的精确值。[输入输出举例］EXAM4.SAM823639837423EXAM4.SAM2170『题意分析』1)任务：求在长度为n的数中添加m个加号的最小值2)程序名exam4.pas3)输入i.文件名exam4.inii.格式及内容第一行数字串n=200（数字串中间无空格且不折行）第二行整数Mm=20（所要添加的加号个数）4)输出i.文件名exam4.outii.格式及内容所求得的最小和的精确值5)数据范围N=200,m=20□注：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。『算法分析』1)根据样例模拟求解过程。-3-11919121391)1,5(19391)1,4(211191)1,3(91939191)1,2(139)2,6(fffff12009)0,4(13819)0,3(930919)0,2(1901919)0,1(138)1,5(fffff209)0,2(2019)0,1(20)1,3(21)0,1()1,2(fffff1201)0,3(10291)0,2(192191)0,1(102)1,4(ffff2)根据数据范围估算程序复杂度。3)Dp简单分析这道题遇到了2个问题：DP和高精度。DP首先，我们要明确添加号的顺序，定序，排除重复的我们只关心最后一个“+”添加的位置。最后一个“+”加完后，“+”左添加（m-1）个加号，而“+”的右侧一定为一个数值。我的程序由递归实现高精度由于数字串的长度最长为200位所以，不免会遇到高精度加法的运算。首先记住第一位表示个位，n表示最高位，所有高精度算法程序都是1为数的最低位fillchar(c,sizeof(c),0);ifa[0]b[0]thenlen:=a[0]elselen:=b[0];{a[0]&b[0]各存储的是a&b的长度,len为想加运算的总长度}fori:=1tolendobegininc(c[i],a[i]+b[i]);ifc[i]10thenbegindec(c[i],10);inc(c[i+1]);end;{进位,由于是递归程序，进位的处理非常简单}end;ifc[len+1]0theninc(len);{如果最高位需要进位，那么len+1}c[0]:=len;{总长度附值}4)函数定义设F(i,j)表示1~i的数字串中添加j个加号的最小值5)所求F（n,m）即为所求N表示数字串的长度，m表示所添加的加号的个数，str1表示数字串6)转移方程0jikstrjkf0jistrjifikj))~1(1)1,(()~1(1),(min1『程序框架』1、描述数据数组的定义和含义；重要常量、变量的含义。-4-TypeArr1=Array[1..200]OfInteger;{数字串最长为200位}ConstInfile='exam4.in';Outfile='exam4.out';VarData:Array[1..200,0..20]OfString;{添加的加号在0~20之间}n,m,i,j:Integer;str1:String;2、输入部分Readln(str1);{读入数字串并求出其长度}n:=Length(str1);Readln(m);3、主程序1）初始化；预处理Fori:=1TonDoForj:=0TomDodata[i,j]:='';{循环赋空}2）实现算法程序DPProceduretry1(i,j:Integer);Vark:Integer;strr1,strr2,min,mink:String;BeginIfj=0ThenBegindata[i,j]:=Copy(str1,1,i);Exit;End;Ifdata[j,j-1]=''Thentry1(j,j-1);{把第一个数认为是最小值}strr1:=data[j,j-1];strr2:=Copy(str1,j+1,i-j);Plus(strr1,strr2,min);Fork:=j+1Toi-1DoBegin{求出最小值}Ifdata[k,j-1]=''Thentry1(k,j-1);strr1:=data[k,j-1];strr2:=Copy(str1,k+1,i-k);Plus(strr1,strr2,mink);IfCheck(min,mink)Thenmin:=mink;End;data[i,j]:=min;{赋给data[i，j]}End;-5-高精度（在前面算法分析已经对程序进行注释）Procedureplus(str1,str2:String;Varmin:String);Varl1,l2,l:Integer;a,b,c:Arr1;BeginFillchar(a,SizeOf(a),0);Fillchar(b,SizeOf(b),0);l1:=Length(str1);l2:=Length(str2);Fori:=1Tol1Doa[i]:=Ord(str1[l1-i+1])-48;Fori:=1Tol2Dob[i]:=Ord(str2[l2-i+1])-48;Ifl1l2Thenl:=l1Elsel:=l2;c[1]:=0;Fori:=1TolDoBeginc[i]:=c[i]+a[i]+b[i];c[i+1]:=c[i]Div10;c[i]:=c[i]Mod10;End;Ifc[l+1]0ThenInc(l);min:='';Fori:=lDownTo1Domin:=min+Chr(c[i]+48);End;4、输出部分1）最优值try1(n,m);Writeln(data[n,m]);2）方案用递归实现。『程序实现』1.递归实现Programexam4;TypeArr1=Array[1..200]OfInteger;ConstInfile='exam4.in';Outfile='exam4.out';VarData:Array[1..200,0..20]OfString;n,m,i,j:Integer;-6-str1:String;Functioncheck(a,b:String):Boolean;Varl1,l2:Integer;Begincheck:=True;l1:=Length(a);l2:=Length(b);Ifl1l2Thencheck:=False;If(l1=l2)And(ab)Thencheck:=False;End;Procedureplus(str1,str2:String;Varmin:String);Varl1,l2,l:Integer;a,b,c:Arr1;BeginFillchar(a,SizeOf(a),0);Fillchar(b,SizeOf(b),0);l1:=Length(str1);l2:=Length(str2);Fori:=1Tol1Doa[i]:=Ord(str1[l1-i+1])-48;Fori:=1Tol2Dob[i]:=Ord(str2[l2-i+1])-48;Ifl1l2Thenl:=l1Elsel:=l2;c[1]:=0;Fori:=1TolDoBeginc[i]:=c[i]+a[i]+b[i];c[i+1]:=c[i]Div10;c[i]:=c[i]Mod10;End;Ifc[l+1]0ThenInc(l);min:='';Fori:=lDownTo1Domin:=min+Chr(c[i]+48);End;Proceduretry1(i,j:Integer);Vark:Integer;strr1,strr2,min,mink:String;Begin-7-Ifj=0ThenBegindata[i,j]:=Copy(str1,1,i);Exit;End;Ifdata[j,j-1]=''Thentry1(j,j-1);strr1:=data[j,j-1];strr2:=Copy(str1,j+1,i-j);Plus(strr1,strr2,min);r:=I–IDiv(j+1)Ifr+1j+1Thenl:=r+1;Ifr-1IThenr:=r–1;Fork:=lTorDoBeginIfdata[k,j-1]=''Thentry1(k,j-1);strr1:=data[k,j-1];strr2:=Copy(str1,k+1,i-k);Plus(strr1,strr2,mink);IfCheck(min,mink)Thenmin:=mink;End;data[i,j]:=min;End;BeginAssign(Input,infile);Reset(Input);Assign(Output,outfile);Rewrite(Output);Readln(str1);n:=Length(str1);Readln(m);Fori:=1TonDoForj:=0TomDodata[i,j]:='';try1(n,m);Writeln(data[n,m]);Close(Input);Close(Output);End.1.递推实现-8-『测试结果和修改』我的程序已经修改正确『总结』1.对问题的理解2.注意事项注意到数据范围，考虑到运用高精度运算3.问题的优化这里加个优化因为添加号应该是把数字串平分才是最好的,.但有时也会出现特例,.所以只是在平方的左右浮动,.但不会浮动太大r:=I–IDiv(j+1)Ifr+1j+1Thenl:=r+1;Ifr-1IThenr:=r–1;4.题目的扩展这道题是跟添乘号是一个类型。只不过添乘号用的是高精度乘法-9-2、乘积最大『题目描述』今年是国际数学联盟确定的“2000—世界数学年”，又恰逢我国著名数学家华罗先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出—种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：3*12＝363l*2＝62这时，符合题目要求的结果是：3l*2=62现在