资源描述：
《动态规划总结汇总(NOIP必备).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、动态规划（一）05B张婕目录一、数字添加号………………………………………………………………-2-二、乘积最大……………………………………………………………………-9-三、矩阵取数……………………………………………………………………-16-四、邮局（已修改）…………………………………………………-22-五、棋盘分割……………………………………………………………………-28-六、矩阵连乘……………………………………………………………………-35-七、能量项链……………………………………………………………………-40-八、石子合并…………………………………………………
2、…………………-45-九、加分二叉树………………………………………………………………-51-十、CUTTING（已修改）………………………………………………-56-1、数字添加号『题目描述』一个由数字1，2，...，9组成的数字串（长度不超过200），问如何将M(M<=20)个加号("+")插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。[输入
3、格式］从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。[输出格式］在屏幕上输出所求得的最小和的精确值。[输入输出举例］EXAM4.SAM3EXAM4.SAM2170『题意分析』1)任务：求在长度为n的数中添加m个加号的最小值2)程序名exam4.pas3)输入i.文件名exam4.inii.格式及内容第一行数字串n<=200（数字串中间无空格且不折行）第二行整数Mm<=20（所要添加的加号个数）4)输出i.文件名exam4.outii.格式及内容所求得的最小和的精确值5)数据范围N<=200,m<=2
4、0：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。『算法分析』1)根据样例模拟求解过程。21)根据数据范围估算程序复杂度。2)Dp简单分析这道题遇到了2个问题：DP和高精度。nDP首先，我们要明确添加号的顺序，定序，排除重复的我们只关心最后一个“+”添加的位置。最后一个“+”加完后，“+”左添加（m-1）个加号，而“+”的右侧一定为一个数值。我的程序由递归实现n高精度由于数字串的长度最长为200位所以，不免会遇到高精度加法的运算。首先记住第一位表示个位，n表示最高位，所有高精度算法程序都是1为数的最低位fillch
5、ar(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;{总长度附值}3)函数定义设F(i,j)表示1~i的数
6、字串中添加j个加号的最小值4)所求F（n,m）即为所求N表示数字串的长度，m表示所添加的加号的个数，str1表示数字串5)转移方程『程序框架』1、描述数据数组的定义和含义；重要常量、变量的含义。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;1、输入部分Readln(str1);{读入
7、数字串并求出其长度}n:=Length(str1);Readln(m);2、主程序1）初始化；预处理Fori:=1TonDoForj:=0TomDodata[i,j]:='';{循环赋空}2）实现算法程序uDPProceduretry1(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[
8、j,j-1];strr2
