中华中学动态规划讲义

1、中华中学动态规划讲义介绍介绍动态规划是NOIP中非常重要的一类题型。在动态规划中，算法是最难想到的，当你想到了算法，实现也就迎刃而解。今天，我们将强调算法的研究，不作上机实践中华中学动态规划讲义递推递推递推是动态规划的根本，我们首先花一点时间进行递推训练中华中学动态规划讲义中华中学动态规划讲义解决递推问题有三个重点：解决递推问题有三个重点：一、如何建立正确的递推关系一、如何建立正确的递推关系二、递推关系有何性质二、递推关系有何性质三、递推关系式如何求解三、递推关系式如何求解递推按照我们推导问题的方向，常分为顺推法递推按照我们推导问题的方向，常分为顺推法和倒推法。和倒推法。中华中学动态规划讲义例

2、例1、有一只经过训练的蜜蜂只能爬向右侧相邻的、有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂爬到蜂房房b的可能路线数。的可能路线数。 中华中学动态规划讲义 问题分析：这是一道很典型的问题分析：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向蜜蜂只能爬向右侧相邻的蜂房，不能反向爬爬行行”的限制，决定了蜜蜂到的限制，决定了蜜蜂到b点的路径只能是点的路径只能是从从b-1点或点或b-2点到达的，故点到达的，故fn=fn-1+fn-2

3、 (a+2=n=b)，边界条件，边界条件fa=1，fa+1=1。 中华中学动态规划讲义例例2 2、打印杨晖三角形的前、打印杨晖三角形的前1010行。杨晖三角形行。杨晖三角形的前的前5 5行如左下图所示。行如左下图所示。 问题分析：我们观察左上图不太容易找问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）发现杨辉三角形其实就是一个二维表（数组）的下三角部分。的下三角部分。中华中学动态规划讲义假设用二维数组假设用二维数组yhyh存储，每行首尾元素都为存储，每行首尾元素都为1 1，且，且其中任意一

4、个非首尾元素其中任意一个非首尾元素yhi,jyhi,j的值其实就是的值其实就是yhi-1,j-1yhi-1,j-1与与yhi-1,jyhi-1,j的和，另外每一行的的和，另外每一行的元素个数刚好等于行数。有了这些规律，给数元素个数刚好等于行数。有了这些规律，给数组元素赋值就不难了，而要打印杨晖三角形，组元素赋值就不难了，而要打印杨晖三角形，只需控制一下每行输出的起始位置即可。只需控制一下每行输出的起始位置即可。中华中学动态规划讲义例例3 3、猴子第、猴子第1 1天摘下若干个桃子天摘下若干个桃子, ,当即吃了一半当即吃了一半又一个。第又一个。第2 2天又把剩下的桃吃了一半又一个天又把剩下的桃吃了

5、一半又一个, ,以以后每天都吃前一天剩下的桃子的一半又一个后每天都吃前一天剩下的桃子的一半又一个, ,到到第第1010天猴子想吃时天猴子想吃时, ,只剩下一个桃子。只剩下一个桃子。 问猴子第问猴子第1 1天一共摘了多少桃子天一共摘了多少桃子? ? 问题分析：问题分析： 已知条件第已知条件第 10 10 天剩下天剩下 1 1 个桃子，隐含个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的条件每一次前一天的桃子个数等于后一天桃子的个数加个数加 1 1 的的 2 2 倍。倍。 我们采取逆向思维的方法我们采取逆向思维的方法, ,从后往前推，从后往前推，可用倒推法求解。可用倒推法求解。中华中学动态规

6、划讲义VarVar S,I:LongInt; S,I:LongInt;BeginBegin S:=1; S:=1;第第1010天只有一个桃子天只有一个桃子 For I:=9 DownTo 1 Do For I:=9 DownTo 1 Do S:=(S+1) S:=(S+1)* *2;2;第第1010天依次求前一天的天依次求前一天的桃桃 Writeln(S); Writeln(S); 子数子数 End.End.中华中学动态规划讲义程序填空：设有一个程序填空：设有一个n n级的楼梯级的楼梯(1=n=12),(1=n=12),编号编号从下到上依次为从下到上依次为1 1至至n,n,其中有若干级为坏的。

7、有其中有若干级为坏的。有一个人上楼梯时一步可走一个人上楼梯时一步可走1 1级、或级、或2 2级、或级、或3 3级级( (坏级只能跨过不能踏上坏级只能跨过不能踏上, ,但级数照算但级数照算) )。问。问: :这个这个人从楼下走到第人从楼下走到第n n级级, ,共有多少种不同的走法共有多少种不同的走法? ?例如例如: :当当n=ln=l时时( (无坏级情况下无坏级情况下),),仅有仅有1 1种走法种走法n=2n=2时时( (无坏级情况下无坏级情况下),),有有:1:1级级+l+l级级 或或 2 2级级 共共2 2种种走法走法n=3n=3时时( (第二级为坏级情况下第二级为坏级情况下),),有有:1

8、:1级级+2+2级级, ,直接直接3 3级级, ,共共2 2种走法种走法【程序说明程序说明】用递推方法求解。用集合记录坏级用递推方法求解。用集合记录坏级。中华中学动态规划讲义var x,i,n,fl,f2,f3,f4:longint;s:set of 0.30;begin readln(n);s:= readln(x);x:坏级坏级,以以0结束结束 while (xO)do begin s:= readln(x); end; If (1 in s) then f1:=0 else fl:=1; If (2 in s) then f2:=0 else f2:= If (3 in s) then

9、f3:=0 else f3:=1+f1+f2;中华中学动态规划讲义 if n=1 then f4:=f1 else if n=2 then f4:=f2 else if n=3 then f4:=f3 else begin for i:=4 to n do begin if(i in s)then f4:=0 else f4:= fl:=f2;f2:=f3;f3:=f4; end; end; writeln(f4);readln;end. 中华中学动态规划讲义例例4、棋盘上、棋盘上A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B点。点。卒行走的规则：可以向下、或者向右。同时在棋盘卒

10、行走的规则：可以向下、或者向右。同时在棋盘上上C点有一个对方的马，该马所在的点和所有跳跃点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为一步可达的点称为对方马的控制点。因此称之为“马马拦过河卒拦过河卒”。棋盘用坐标表示，。棋盘用坐标表示，A点点(0, 0)、B点点(n, m)(n, m为不超过为不超过15的整数的整数)，同样马的位置坐标是，同样马的位置坐标是需要给出的。现在要求你计算出卒从需要给出的。现在要求你计算出卒从A点能够到达点能够到达B点的路径的条数，假设马的位置是固定不动的，并点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。不是卒走

11、一步马走一步。【样例样例】knight.in knight.out6 6 3 36中华中学动态规划讲义 分析：本题可用搜索算法，但分析：本题可用搜索算法，但N,M=15就会超时就会超时。再分析题意会发现：要到达棋盘上的一个点，只能再分析题意会发现：要到达棋盘上的一个点，只能从左边过来或是从上面过来。根据加法原理，到达从左边过来或是从上面过来。根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。行）递推的方法来求

12、出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为点的路径数目设置为0即可。即可。中华中学动态规划讲义 假设用假设用fi，j表示到达点（表示到达点（i,j）的路径数目，用）的路径数目，用gi,j表示点表示点(i,j)是否是对方马的控制点，是否是对方马的控制点，gi,j=0表示表示不是对方马的控制点，不是对方马的控制点，gi,j=1表示是对方马的控制表示是对方马的控制点。则，我们可以得到如下的递推关系式：点。则，我们可以得到如下的递推关系式： 递推边界为递推边界为f0,0=1,f0,0=1,考虑到最大情况下：考虑到

13、最大情况下： n=20,m=20n=20,m=20，路径条数可能会超出长整数范围所以要，路径条数可能会超出长整数范围所以要使用使用CompComp类型或高精度运算。类型或高精度运算。fi,j=0 gx,y=1fi,j=0 gx,y=1fi,0=fi-1,0 i0,gx,y=0fi,0=fi-1,0 i0,gx,y=0f0,j=f0,j-1 j0,gx,y=0f0,j=f0,j-1 j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0 中华中学动态规划讲义例例5 5、(NOIP(NOIP普及组第四题）给定普

14、及组第四题）给定A,B,CA,B,C三根足够长三根足够长的细柱，在的细柱，在A A柱上放有柱上放有2n2n个中间有空的圆盘，共有个中间有空的圆盘，共有n n个不同的尺寸，每个个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的区分的( (下图为下图为n=3n=3的情形）。现要将的情形）。现要将 这些国盘移这些国盘移到到C C柱上，在移动过程中可放在柱上，在移动过程中可放在B B柱上暂存。要求柱上暂存。要求: : (1)(1)每次只能移动一个圆盘；每次只能移动一个圆盘；(2) A(2) A、B B、C C三根细柱上的圆盘都要保持上小下大

15、三根细柱上的圆盘都要保持上小下大的顺序；的顺序；任务任务: :设设AnAn为为2n2n个圆盘完成上述任务所需的最少移个圆盘完成上述任务所需的最少移动次数，对于输入的动次数，对于输入的n n，输出，输出AnAn。 中华中学动态规划讲义【输入输入】 输入文件输入文件hanoi.inhanoi.in为一个正整数为一个正整数n n，表示，表示在在A A柱上放有柱上放有2n2n个圆盘。个圆盘。 【输出输出】 输出文件输出文件hanoi.outhanoi.out仅一行，包含一个正仅一行，包含一个正整数，为完成上述任务所需的最少移动次数整数，为完成上述任务所需的最少移动次数AnAn。 【输入输出样例输入输出

16、样例1 1】 hanoi.in hanoi.outhanoi.in hanoi.out1 21 2中华中学动态规划讲义问题分析：如果每个尺寸只有一个圆盘，共问题分析：如果每个尺寸只有一个圆盘，共n n个个圆盘，也就是常见的汉诺塔问题。则设圆盘，也就是常见的汉诺塔问题。则设h hn n为为n n 个盘子个盘子从从a a柱移到柱移到c c柱所需移动的盘次。显然，当柱所需移动的盘次。显然，当n=1n=1时，只时，只需把需把a a 柱上的盘子直接移动到柱上的盘子直接移动到c c柱就可以了，故柱就可以了，故h h1 1=1=1。当当n=2n=2时，先将时，先将a a柱上面的小盘子移动到柱上面的小盘子移动

17、到b b柱上去；然柱上去；然后将大盘子从后将大盘子从a a柱移到柱移到c c 柱；最后，将柱；最后，将b b柱上的小盘子柱上的小盘子移到移到c c柱上，共记柱上，共记3 3个盘次，故个盘次，故h h2 2=3=3。以此类推，当。以此类推，当a a柱上有柱上有n(n=2)n(n=2)个盘子时，总是先借助个盘子时，总是先借助c c柱把上面的柱把上面的n-n-1 1个盘子移动到个盘子移动到b b柱上，然后把柱上，然后把a a柱最下面的盘子移动柱最下面的盘子移动到到c c柱上；再借助柱上；再借助a a柱把柱把b b柱上的柱上的n-1n-1个盘子移动到个盘子移动到c c柱柱上；总共移动上；总共移动h h

18、n-1n-1+1+h+1+hn-1n-1个盘次。个盘次。 h hn n=2h=2hn-1n-1+1 +1 边界条件：边界条件：h hn-1n-1=1=1中华中学动态规划讲义该题若仔细观察，很容易发现是该题若仔细观察，很容易发现是hanoi塔的变形塔的变形（只不过多了几个盘子），操作过程中，可以（只不过多了几个盘子），操作过程中，可以将两个相同尺寸的盘子看成一个整体，这样就将两个相同尺寸的盘子看成一个整体，这样就成了典型的成了典型的hanoi塔问题。再运用公式：塔问题。再运用公式：fn=2n-1来做，最后只要乘来做，最后只要乘2就行了。由于数据就行了。由于数据较大，须用到高精度运算。较大，须用到

19、高精度运算。中华中学动态规划讲义题型大类题型大类简单线性dp背包最长XX子序列最长公共子序列LCS区间dp树dp坐标dp。中华中学动态规划讲义1.数塔数塔 7 3 8 8 1 0 2 7 7 4 5 5 2 6 5如图，有一数字三角形。数字三角形中的数字为不超过100的正整数。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。此数塔输出为30中华中学动态规划讲义是否可以用前两次课所用的深搜呢。显然前两次课的深搜写数塔这道题的时候程序

20、简明易懂。但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。const maxn=10;var a:array1.maxn,1.maxn of integer; max:longint;n,i,j:integer;procedure try(x,y,dep:integer;sum:longint);begin if (dep=n) then begin if summax then max:=sum; exit end; try(x+1,y,dep+1,sum+ax+1,y); try(x+1,y+1,de

21、p+1,sum+ax+1,y+1);end;begin readln(n); for i:=1 to n do for j:= 1 to i do read(ai,j); max:=0; try(1,1,1,a1,1); writeln(max);end.中华中学动态规划讲义那我们又该如何实现动态 规划呢？中华中学动态规划讲义1.逆推法:按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最佳路径。设：fi,j为从第i阶段中的点j至第n行的

22、最大的数字和；则: fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=jfi+1,j+1 then fi,j:=ai,j+fi+1,j else fi,j:=ai,j+fi+1,j+1; writeln(f1,1);end. 中华中学动态规划讲义2. 顺推法按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4，5,.,.n-1,n到起点的最大和,最后找第n行的最大值设fi,j为 第i行第j列上点到起点的最大和则 f1，1=a1,1; fi，1=ai, 1+fi-1,

23、1; f i，j =max ai,j+fi-1,j-1,ai,j+fi-1,j 2=jfi-1,j then fi,j:=ai,j+fi-1,j-1 else fi,j:=ai,j+fi-1,j; end; maxsum:=0; for i:=1 to n do if fn,imaxsum then maxsum:=fn,i; writeln(maxsum);end.中华中学动态规划讲义2.最长不下降子序列最长不下降子序列设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3 ie 且有a(i1)a(i

24、2) a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。中华中学动态规划讲义const maxn=100;var a,b,c:array1.maxn of integer; n,i,j,max,p:integer;begin readln(n); for i:=1 to n do begin read(ai); bn:=1; cn:=0; end; for i:= n-1 downto 1 do begin max:=0;p:=0; for

25、 j:=i+1 to n do if (aimax) then begin max:=bj;p:=j end; if p0 then begin bi:=bp+1;ci:=p end end; max:=0;p:=0; for i:=1 to n do if bimax then begin max:=bi;p:=i end; writeln(maxlong=,max); while p0 do begin write(ap:5);p:=cp end;end.中华中学动态规划讲义谁能够说出刚刚做法的时间复杂度？n2有没有速度更快的做法呢有！下面介绍nlogn的算法中华中学动态规划讲义var n

26、,i,ans,j,k,m:longint; a,b:array1.10000 of longint;begin read(n); for i := 1 to n do read(ai); ans:=0; for i := 1 to n do begin j:=1;k:=ans; while j = k do begin m:=(j+k) div 2; if bmans then inc(ans); bj:=ai; end; writeln(ans);end.中华中学动态规划讲义同样的道理我们也可以做最长不上升子序列等等最长XX子序列中华中学动态规划讲义3.背包问题背包问题1.部分背包问题 一个

27、旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，.,Wn,它们的总价值分别为C1,C2,.,Cn.求旅行者能获得最大总价值。 解决问题的方法是贪心算法:将C1/W1,C2/W2,.Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止. 中华中学动态规划讲义 2.0/1背包 一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。 分析说明: 显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制). 程序简单,但

28、是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数 设 f(i，x)表示前i件物品，总重量不超过x的最优价值 则 f（i，x）=max(f(i1，x-Wi)+Ci，f（i1，x） f（n，m）即为最优解，边界条件为f（0，x）0 ，f(i,0)=0; 中华中学动态规划讲义 const maxm=200;maxn=30; type ar=array1.maxn of integer; var m,n,j,i:integer; c,w:ar; f:array0.maxn,0.maxm of integer; function max(

29、x,y:integer):integer; begin if xy then max:=x else max:=y; end; begin readln(m,n); for i:= 1 to n do readln(wi,ci); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j=wi then fi,j:=max(fi-1,j-wi+ci,fi-1,j) else fi,j:=fi-1,j; end; writeln(fn,m); end.

30、中华中学动态规划讲义3.完全背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，.,Wn,每件的价值分别为C1,C2,.,Cn.若的每种物品的件数足够多.求旅行者能获得的最大总价值。本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x）=maxf(x-wi)+ci 当x=wi 1=i=n思考：我们该如何把01背包改成完全背包呢？中华中学动态规划讲义4.采药采药辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对

31、他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？中华中学动态规划讲义4.采药采药【输入文件】输入文件medic.in的第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic

32、.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】 70 3 71 100 69 1 1 2【样例输出】3【数据规模】对于30%的数据，M = 10；对于全部的数据，M = 100。中华中学动态规划讲义5.开心的金明开心的金明金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，

33、第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。中华中学动态规划讲义5.开心的金明开心的金明【输入文件】输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：N m（其中N（30000）表示总钱数，m（25）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1

34、的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格(v=10000)，p表示该物品的重要度(15)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900中华中学动态规划讲义6.金明的预算方案金明的预算方案金明今天很开心，家里购置的新房就要领钥匙了，新房里金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天

35、对他说：妈妈昨天对他说：“你的房间需要购买哪些物品，怎么你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过布置，你说了算，只要不超过N元钱就行元钱就行”。今天一早，。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件与附件的例子：主件 附件电脑附件电脑 打印机，扫描仪书柜打印机，扫描仪书柜 图图书书桌书书桌 台灯，文具工作椅台灯，文具工作椅 无如果要买归类为附件无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主

36、件可以有的物品，必须先买该附件所属的主件。每个主件可以有0个、个、1个或个或2个附件。附件不再有从属于自己的附件。个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的金明想买的东西很多，肯定会超过妈妈限定的N元。于元。于是，他把每件物品规定了一个重要度，分为是，他把每件物品规定了一个重要度，分为5等：用整等：用整数数15表示，第表示，第5等最重要。他还从因特网上查到了每件等最重要。他还从因特网上查到了每件物品的价格（都是物品的价格（都是10元的整数倍）。他希望在不超过元的整数倍）。他希望在不超过N元（可以等于元（可以等于N元）的前提下，使每件物品的价格与重元）的前提下，

37、使每件物品的价格与重要度的乘积的总和最大。设第要度的乘积的总和最大。设第j件物品的价格为件物品的价格为vj，重要度为重要度为wj，共选中了，共选中了k件物品，编号依次为件物品，编号依次为j1，j2，jk，则所求的总和为：，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中。（其中*为乘为乘号）请你帮助金明设计一个满足要求的购物单。号）请你帮助金明设计一个满足要求的购物单。中华中学动态规划讲义6.金明的预算方案金明的预算方案【输入文件输入文件】 输入文件的第输入文件的第1行，为两个正整数，用一行，为两个正整数，用一个空格隔开：个空格隔开： N m 其中其中N（32000）

38、表示总钱数，）表示总钱数，m（60）为希望购买物品的个数。）为希望购买物品的个数。） 从第从第2行到第行到第m+1行，第行，第j行给出了编号为行给出了编号为j-1的物品的基本数据，每的物品的基本数据，每行有行有3个非负整数个非负整数 v p q （其中（其中v表示该物品的价格表示该物品的价格（v0，表示该物品为附件，表示该物品为附件，q是所属主件的编号）是所属主件的编号）【输出文件输出文件】输出文件只有一个正整数，为不超过总钱输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值数的物品的价格与重要度乘积的总和的最大值 （=ai,0) and (fi,j=(ai,0+ai

39、,1) and (fi,j=(ai,0+ai,2) and (fi,j=(ai,0+ai,1+ai,2) and (fi,jdi,j-1 then di,j:=di-1,j else di,j:=di,j-1; end; 下面我们给出一个基本的程序段中华中学动态规划讲义8.回文词回文词【题目描述】（vijos1327） 回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。 比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文

40、词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。中华中学动态规划讲义【输入格式】 第一行包含一个整数N，表示给定字符串的长度，3=Ny then exit(x) else exit(y); end;Begin readln(n); for i:=1 to n dobegin read(ai); bn-i+1:=ai; /制作S2end; for i:=1 to n do /LCS for j:=1 to n do if ai=bj then fi,j:=fi-1,j-1+1 else fi,j:=max(fi-1,j,fi,j-1);writeln

41、(n-fn,n); /输出需要配对的字符数 end.中华中学动态规划讲义思考题： 如果是3个字符串求最长公共子序列又该怎么做呢？中华中学动态规划讲义9.区间区间dp合并：意思就是将两个或多个部分进行整合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个合，当然也可以反过来，也就是是将一个问题进行分解成两个或多个部分。问题进行分解成两个或多个部分。特征：能将问题分解成为两两合并的形式特征：能将问题分解成为两两合并的形式求解：对整个问题设最优值，枚举合并点，求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左将问题分解成为左右两个部分，最后将左右两个部分的

42、最优值进行合并得到原问题右两个部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。的最优值。有点类似分治算法的解题思想。典型试题：整数划分，凸多边形划分、石典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。子合并、多边形合并、能量项链等。中华中学动态规划讲义10.整数划分整数划分给出一个长度为给出一个长度为n的数的数要在其中加要在其中加m-1个乘号，分成个乘号，分成m段段这这m段的乘积之和最大段的乘积之和最大mn=20有有T组数据，组数据，T=10000中华中学动态规划讲义10.整数划分整数划分给出一个长度为给出一个长度为n的数的数要在其中加要在其中加m-1个

43、乘号，分成个乘号，分成m段段这这m段的乘积之和最大段的乘积之和最大mn=20有有T组数据，组数据，T=10000中华中学动态规划讲义10.整数划分整数划分可以先预处理出原数第可以先预处理出原数第i到到j段的数值段的数值Ai,j是是多少，这样转移就方便了，预处理也要尽多少，这样转移就方便了，预处理也要尽量降低复杂度。量降低复杂度。Fi，j表示把这个数前表示把这个数前i位分成位分成j段得到的最段得到的最大乘积。大乘积。Fi,j=Fk,j-1*Ak+1,i,1ki=n, j2,maxint*500); readln(n); for i:=1 to n do begin read(mapi); mapi+n:=mapi; end; for i:=1 to 2*n do begin fi,i:=0; gi,i:=0; end;end;中华中学动态规划讲义function sum(a,b:longint):longint;var i:longint;begin sum:=0; for i:=a to b do inc(sum,mapi); exit(sum);end;function max(a,b:longint):longint;begin if ab then exit(a) else exit(b);end;functio