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

1、动态规划 （一）05B 张婕 目录一、 数字添加号-2-二、 乘积最大-9-三、 矩阵取数-16-四、 邮局 （已修改）-22-五、 棋盘分割-28-六、 矩阵连乘-35-七、 能量项链-40-八、 石子合并-45-九、 加分二叉树-51-十、 CUTTING（已修改）-56-1、 数字添加号题目描述一个由数字1，2，. ，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需

2、要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。输入格式从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。输出格式在屏幕上输出所求得的最小和的精确值。输入输出举例EXAM4.SAM3EXAM4.SAM 2170题意分析1) 任务 ：求在长度为n的数中添加m 个加号的最小值2) 程序名 exam4.pas3) 输入i. 文件名 exam4.inii. 格式及内容 第一行 数字串 n=200（数字串中间无空格且不折行）第二行 整数M m = 20（所要添加的加号个数）4) 输出i. 文件名 exam4.outii. 格式及

3、内容 所求得的最小和的精确值5) 数据范围N = 200, m b0 then len:=a0 else len:=b0;a0&b0各存储的是a&b的长度,len为想加运算的总长度 for i:=1 to len do begin inc(ci,ai+bi);if ci10 then begin dec(ci,10); inc(ci+1); end; 进位,由于是递归程序，进位的处理非常简单end; if clen+10 then inc(len);如果最高位需要进位，那么len+1 c0:=len;总长度附值4) 函数定义设F(i, j)表示1 i的数字串中添加j个加号的最小值5) 所求F（

4、n, m）即为所求N表示数字串的长度，m表示所添加的加号的个数，str1表示数字串6) 转移方程程序框架1、 描述数据数组的定义和含义；重要常量、变量的含义。Type Arr1 = Array1.200 Of Integer; 数字串最长为200位Const Infile = exam4.in; Outfile = exam4.out;Var Data: Array1.200, 0.20 Of String; 添加的加号在020之间 n, m, i, j: Integer; str1: String;2、 输入部分 Readln(str1); 读入数字串并求出其长度 n := Length(s

5、tr1); Readln(m);3、 主程序1） 初始化；预处理For i:=1 To n Do For j:=0 To m Do datai, j := ; 循环赋空2） 实现算法程序u DPProcedure try1(i, j: Integer);Var k: Integer; strr1, strr2, min, mink: String;Begin If j = 0 Then Begin datai, j := Copy(str1, 1, i); Exit; End; If dataj, j - 1 = Then try1(j, j - 1); 把第一个数认为是最小值 strr1 :

6、= dataj, j - 1; strr2 := Copy(str1, j + 1, i - j); Plus(strr1, strr2, min); For k:=j+1 To i-1 Do Begin 求出最小值 If datak, j - 1 = Then try1(k, j - 1); strr1 := datak, j - 1; strr2 := Copy(str1, k + 1, i - k); Plus(strr1, strr2, mink); If Check(min, mink) Then min := mink; End; datai, j := min; 赋给datai，

7、jEnd;u 高精度（在前面算法分析已经对程序进行注释）Procedure plus(str1, str2: String; Var min: String);Var l1, l2, l: Integer; a, b, c: Arr1;Begin Fillchar(a, SizeOf(a), 0); Fillchar(b, SizeOf(b), 0); l1 := Length(str1); l2 := Length(str2); For i:=1 To l1 Do ai := Ord(str1l1 - i + 1) - 48; For i:=1 To l2 Do bi := Ord(str2

8、l2 - i + 1) - 48; If l1 l2 Then l := l1 Else l:= l2; c1 := 0; For i:=1 To l Do Begin ci := ci + ai + bi; ci + 1 := ci Div 10; ci := ci Mod 10; End; If cl + 1 0 Then Inc(l); min := ; For i:=l DownTo 1 Do min := min + Chr(ci + 48);End;4、 输出部分1） 最优值try1(n, m); Writeln(datan, m);2） 方案用递归实现。程序实现1. 递归实现Pr

9、ogram exam4;Type Arr1 = Array1.200 Of Integer;Const Infile = exam4.in; Outfile = exam4.out;Var Data: Array1.200, 0.20 Of String; n, m, i, j: Integer; str1: String;Function check(a, b: String): Boolean;Var l1, l2: Integer;Begin check := True; l1 := Length(a); l2 := Length(b); If l1 l2 Then check := F

10、alse; If (l1 = l2) And (a l2 Then l := l1 Else l:= l2; c1 := 0; For i:=1 To l Do Begin ci := ci + ai + bi; ci + 1 := ci Div 10; ci := ci Mod 10; End; If cl + 1 0 Then Inc(l); min := ; For i:=l DownTo 1 Do min := min + Chr(ci + 48);End;Procedure try1(i, j: Integer);Var k: Integer; strr1, strr2, min,

11、mink: String;Begin If j = 0 Then Begin datai, j := Copy(str1, 1, i); Exit; End; If dataj, j - 1 = Then try1(j, j - 1); strr1 := dataj, j - 1; strr2 := Copy(str1, j + 1, i - j); Plus(strr1, strr2, min); r := I I Div (j + 1) If r+1 j + 1 Then l := r + 1; If r-1 j + 1 Then l := r + 1; If r-1 1) and (cl

12、en=0) do dec(len); 若不需进位则调整len，因为有可能出现0的情况 c0:=len; 4) 函数定义设F(i, j)表示1 i的数字串中添加j个乘号的最大值5) 所求F（n, k）即为所求N表示数字串的长度，k表示所添加的加号的个数，str1表示数字串6) 转移方程程序框架1. 描述数据a) 数组的定义和含义；重要常量、变量的含义。Type Arr1 = Array1.40 Of Integer; Arr2 = Array1.80 Of Integer; 高精度乘法位数最高位是两个数相加Const Infile = exam2.in; Outfile = exam2.out;

13、Var Data: Array1.40, 0.6 Of String; n, k, i, j: Integer; str1: String;2. 输入部分Readln(n, k); Readln(str1); 读入数字串3. 主程序a) 初始化；预处理 For i:=1 To n Do For j:=0 To k Do datai, j := ; 循环赋空b) 实现算法程序u 高精度（在前面算法分析已经对程序进行注释）Procedure Mult(str1, str2: String; Var max: String);Var l1, l2, l: Integer; a, b, c: Arr1

14、;Begin Fillchar(a, SizeOf(a), 0); Fillchar(b, SizeOf(b), 0); Fillchar(c, SizeOf(c), 0); l1 := Length(str1); l2 := Length(str2); For i:=1 To l1 Do ai := Ord(str1l1 - i + 1) - 48; For i:=1 To l2 Do bi := Ord(str2l2 - i + 1) - 48; For i:=1 To l1 Do For j:=1 To l2 Do Begin ci + j - 1 := ci + j - 1 + ai

15、* bj; ci + j := ci + j + ci + j - 1 Div 10; ci + j - 1 := ci + j - 1 Mod 10; End; l := l1 + l2; If cl = 0 Then Dec(l); max := ; For i:=l DownTo 1 Do max := max + Chr(ci + 48);End;u DPProcedure try1(i, j: Integer);Var k: Integer; strr1, strr2, max, maxk: String;Begin If j = 0 Then Begin datai, j := C

16、opy(str1, 1, i); Exit; End; If dataj, j - 1 = Then try1(j, j - 1); 认为第一个数为最大值 strr1 := dataj, j - 1; strr2 := Copy(str1, j + 1, i - j); Mult(strr1, strr2, max); For k:=j+1 To i-1 Do Begin 循环找出最大值 If datak, j - 1 = Then try1(k, j - 1); strr1 := datak, j - 1; strr2 := Copy(str1, k + 1, i - k); Mult(st

17、rr1, strr2, maxk); If Check(max, maxk) Then max := maxk; End; datai, j := max; 赋给datai，jEnd;4. 输出部分a) 最优值try1(n, k); Writeln(datan, k); b) 方案用递归实现。程序实现1、递归实现Program exam2;Type Arr1 = Array1.40 Of Integer; Arr2 = Array1.80 Of Integer;Const Infile = exam2.in; Outfile = exam2.out;Var Data: Array1.40, 0

18、.6 Of String; n, k, i, j: Integer; str1: String;Function check(a, b: String): Boolean;Var l1, l2: Integer;Begin check := True; l1 := Length(a); l2 := Length(b); If l1 l2 Then check := False; If (l1 = l2) And (a b) Then check := False;End;Procedure Mult(str1, str2: String; Var max: String);Var l1, l2

19、, l: Integer; a, b, c: Arr1;Begin Fillchar(a, SizeOf(a), 0); Fillchar(b, SizeOf(b), 0); Fillchar(c, SizeOf(c), 0); l1 := Length(str1); l2 := Length(str2); For i:=1 To l1 Do ai := Ord(str1l1 - i + 1) - 48; For i:=1 To l2 Do bi := Ord(str2l2 - i + 1) - 48; For i:=1 To l1 Do For j:=1 To l2 Do Begin ci

20、+ j - 1 := ci + j - 1 + ai * bj; ci + j := ci + j + ci + j - 1 Div 10; ci + j - 1 := ci + j - 1 Mod 10; End; l := l1 + l2; If cl = 0 Then Dec(l); max := ; For i:=l DownTo 1 Do max := max + Chr(ci + 48);End;Procedure try1(i, j: Integer);Var k: Integer; strr1, strr2, max, maxk: String;Begin If j = 0 T

21、hen Begin datai, j := Copy(str1, 1, i); Exit; End; If dataj, j - 1 = Then try1(j, j - 1); strr1 := dataj, j - 1; strr2 := Copy(str1, j + 1, i - j); Mult(strr1, strr2, max); For k:=j+1 To i-1 Do Begin If datak, j - 1 = Then try1(k, j - 1); strr1 := datak, j - 1; strr2 := Copy(str1, k + 1, i - k); Mul

22、t(strr1, strr2, maxk); If Check(max, maxk) Then max := maxk; End; datai, j := max;End;Begin Assign(Input, infile); Reset(Input); Assign(Output, outfile); Rewrite(Output); Readln(n, k); Readln(str1); For i:=1 To n Do For j:=0 To k Do datai, j := ; try1(n, k); Writeln(datan, k); Close(Input); Close(Ou

23、tput);End. 2、递推实现测试结果和修改 我的程序已经修改正确总结1. 对问题的理解2. 注意事项 注意到数据范围，考虑到运用高精度运算3. 问题的优化4. 题目的扩展这道题是添加号是一个类型。只不过是那道题的延伸3、矩阵取数题目描述矩阵取数游戏（game.pas/c/cpp）【问题描述】帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下：1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素；2. 每次取走的各个元素只能是该元素所在行的行首或行尾；3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数

24、的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4. 游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。【输入】输入文件game.in包括n+1行；第一行为两个用空格隔开的整数n和m。第2n+1行为n*m矩阵，其中每行有m个用单个空格隔开【输出】输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大的分。【输入输出样例1】game.ingame.out2 31 2 43 4 282【输入输出样例1解释】第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6第2次：两行均取行首元素，本

25、次得分为2*22+3*22=20第3次：得分为3*23+4*23=56。总得分为6+20+56=82【限制】60%的数据满足：1=n, m=30，答案不超过1016100%的数据满足：1=n, m=80，0=aij=1000题意分析1) 任务 ： 对于任意矩阵，求出取数后的最大得分2) 程序名 game.pas3) 输入a) 文件名 game.inb) 格式及内容第一行 两个用空格隔开的整数n和m。第2n+1行 其中每行有m个用单个空格隔开 (n*m矩阵)4) 输出c) 文件名 game.outd) 格式及内容 输入矩阵取数后的最大的分5) 数据范围60%的数据满足：1=n, m=30，答案不

26、超过1016100%的数据满足：1=n, m=80，0=aij=1000算法分析1) 根据样例模拟求解过程。【输入输出样例1解释】第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6第2次：两行均取行首元素，本次得分为2*22+3*22=20第3次：得分为3*23+4*23=56。总得分为6+20+56=822) 根据数据范围估算程序复杂度。3) Dp简单分析 由此我们可以知道每行和每一行没有关系，只是最后结果把他们相加就可以了。 我们只对每一行进行处理，由于每次*2i，所以又能优化成叠代法。4) 函数定义 表示第i到第j个数取完后的最大得分5) 所求F(t, m)既为

27、所求 T表示1n行6) 转移方程 程序框架1. 描述数据a) 数组的定义和含义；重要常量、变量的含义。Type arr1 = Array1.30 Of Integer; arr2 = Array1.60 Of Integer;Const Infile = game.in; Outfile = game.out;Var a, data: Array1.80, 1.80 Of String; b: Array1.80 Of String; n, m, i, j, t, k: Integer; str1, ans: String;2. 输入部分Readln(n, m); For i:=1 To n

28、Do Begin Readln(str1); str1 := str1 + ; For j:=1 To m Do Begin ai, j := ; While str11 Do Begin ai, j := ai, j + str11; delete(str1, 1, 1); End; delete(str1, 1, 1); End; End;3. 主程序b) 初始化；预处理ans := ; For t:=1 To n Do Begin For i:=1 To m Do For j:=1 To m Do datai, j := ; try1(1, m); Plus(data1, m, ans,

29、 ans); End;c) 实现算法程序Procedure Try1(i, j: Integer);Var max, max1, max2, strr1, strr2: String;Begin If i = j Then Begin plus(at, i, at, i, datai, j); Exit; End; If datai + 1, j = Then try1(i + 1, j); Plus(datai + 1, j, at, i, strr1); strr2 := strr1; Plus(strr1, strr2, max1); If datai, j - 1 = Then try

30、1(i, j - 1); Plus(datai, j - 1, at, j, strr1); strr2 := strr1; Plus(strr1, strr2, max2); Compare(max1, max2, max); datai, j := max;End;4. 输出部分d) 最优值 Writeln(ans);e) 方案用递归实现。程序实现1、递归实现Program game;Type arr1 = Array1.30 Of Integer; arr2 = Array1.60 Of Integer;Const Infile = game.in; Outfile = game.out

31、;Var a, data: Array1.80, 1.80 Of String; b: Array1.80 Of String; n, m, i, j, t, k: Integer; str1, ans: String;Procedure Compare(a, b: String; Var max: String);Var l1, l2: Integer;Begin l1 := Length(a); l2 := Length(b); If l1 b Then max := a Else max := b; 比大小的时候要注意End;Procedure Plus(la, lb: String;

32、Var lc: String);Var l1, l2, l, i: Integer; a, b, c: Arr1;Begin Fillchar(a, SizeOf(a), 0); Fillchar(b, SizeOf(b), 0); l1 := Length(la); l2 := Length(lb); For i:=1 To l1 Do ai := Ord(lal1 - i + 1) - 48; For i:=1 To l2 Do bi := Ord(lbl2 - i + 1) - 48; If l1 l2 Then l := l2 Else l := l1; c1 := 0; For i:

33、=1 To l Do Begin ci := ci + ai + bi; ci + 1 := ci Div 10; ci := ci Mod 10; End; If cl + 1 0 Then Inc(l); lc := ; For i:=l DownTo 1 Do lc := lc + Chr(ci + 48);End;Procedure Try1(i, j: Integer);Var max, max1, max2, strr1, strr2: String;Begin If i = j Then Begin plus(at, i, at, i, datai, j); 如果*2的话直接加

34、Exit; End; If datai + 1, j = Then try1(i + 1, j); Plus(datai + 1, j, at, i, strr1); strr2 := strr1; Plus(strr1, strr2, max1); If datai, j - 1 = Then try1(i, j - 1); Plus(datai, j - 1, at, j, strr1); strr2 := strr1; Plus(strr1, strr2, max2); Compare(max1, max2, max); datai, j := max;End;Begin Assign(

35、Input, infile); Reset(Input); Assign(Output, outfile); Rewrite(Output); Readln(n, m); For i:=1 To n Do Begin 读入字符串的时候要注意 For j:=1 To m Do Begin Read(ch); AI, j := aI, j + ch;End; Readln; End; ans := ; For t:=1 To n Do Begin For i:=1 To m Do For j:=1 To m Do datai, j := ; try1(1, m); Plus(data1, m, ans, ans); End; Writeln(ans); Close(Input); Close(Output);End.2、递推实现测试结果和修改 我的程序已经修改正确