中华中学动态规划讲义.ppt

《中华中学动态规划讲义.ppt》由会员分享，可在线阅读，更多相关《中华中学动态规划讲义.ppt（73页珍藏版）》请在三一办公上搜索。

1、中华中学动态规划讲义,周默,介绍,动态规划是NOIP中非常重要的一类题型。在动态规划中，算法是最难想到的，当你想到了算法，实现也就迎刃而解。今天，我们将强调算法的研究，不作上机实践,递推,递推是动态规划的根本，我们首先花一点时间进行递推训练,递推关系是一种简洁高效的常见数学模型，比如我们熟悉的Fibonacci数列问题。在这种类型的问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个“递推关系式”来表示的。求解问题时我们从初始的一个或若干个数据项出发，通过递推关系逐步推进，从而得到最终结果，这种求解问题的方法叫“递推法”。其中，初始的若干数据项

2、称为“边界”。,解决递推问题有三个重点：,一、如何建立正确的递推关系二、递推关系有何性质三、递推关系式如何求解,递推按照我们推导问题的方向，常分为顺推法和倒推法。,例1、有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。,问题分析：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的，故fn=fn-1+fn-2(a+2=n=b)，边界条件fa=1，fa+1=1。,例2、打印杨晖三角形的前10行。杨晖三角形的前5行如左下图

3、所示。,问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。,假设用二维数组yh存储，每行首尾元素都为1，且其中任意一个非首尾元素yhi,j的值其实就是yhi-1,j-1与yhi-1,j的和，另外每一行的元素个数刚好等于行数。有了这些规律，给数组元素赋值就不难了，而要打印杨晖三角形，只需控制一下每行输出的起始位置即可。,例3、猴子第1天摘下若干个桃子,当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个,以后每天都吃前一天剩下的桃子的一半又一个,到第10天猴子想吃时,只剩下一个桃子。问猴子第1天一共摘了多少桃子?,问题

4、分析：已知条件第 10 天剩下 1 个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的个数加 1 的 2 倍。我们采取逆向思维的方法,从后往前推，可用倒推法求解。,Var S,I:LongInt;Begin S:=1;第10天只有一个桃子 For I:=9 DownTo 1 Do S:=(S+1)*2;第10天依次求前一天的桃 Writeln(S);子数End.,程序填空：设有一个n级的楼梯(1=n=12),编号从下到上依次为1至n,其中有若干级为坏的。有一个人上楼梯时一步可走1级、或2级、或3级(坏级只能跨过不能踏上,但级数照算)。问:这个人从楼下走到第n级,共有多少种不同的走法?例如:

5、当n=l时(无坏级情况下),仅有1种走法n=2时(无坏级情况下),有:1级+l级 或 2级 共2种走法n=3时(第二级为坏级情况下),有:1级+2级,直接3级,共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)th

6、en 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点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为

7、“马拦过河卒”。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【样例】knight.in knight.out6 6 3 36,分析：本题可用搜索算法，但N,M=15就会超时。再分析题意会发现：要到达棋盘上的一个点，只能从左边过来或是从上面过来。根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该

8、点的路径数目设置为0即可。,假设用fi，j表示到达点（i,j）的路径数目，用gi,j表示点(i,j)是否是对方马的控制点，gi,j=0表示不是对方马的控制点，gi,j=1表示是对方马的控制点。则，我们可以得到如下的递推关系式：,递推边界为f0,0=1,考虑到最大情况下：n=20,m=20，路径条数可能会超出长整数范围所以要使用Comp类型或高精度运算。,fi,j=0 gx,y=1fi,0=fi-1,0 i0,gx,y=0f0,j=f0,j-1 j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0,例5、(NOIP普及组第四题）给定A,B,C三根足够长的细柱，在A柱上

9、放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求:(1)每次只能移动一个圆盘；(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。,【输入】输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。【输入输出样例1】hanoi.in hanoi.out1 2,问题分析：如

10、果每个尺寸只有一个圆盘，共n个圆盘，也就是常见的汉诺塔问题。则设hn为n 个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。hn=2hn-1+1 边界条件：hn-1=1,该题若仔细观察，很容易

11、发现是hanoi塔的变形（只不过多了几个盘子），操作过程中，可以将两个相同尺寸的盘子看成一个整体，这样就成了典型的hanoi塔问题。再运用公式：fn=2n-1来做，最后只要乘2就行了。由于数据较大，须用到高精度运算。,题型大类,简单线性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，编程求解从最顶层走到最底层的一条路径，

12、使得沿着该路径所经过的数字的总和最大，输出最大值。此数塔输出为30,是否可以用前两次课所用的深搜呢。显然前两次课的深搜写数塔这道题的时候程序简明易懂。但是当行数很大时，当三角形的行数等于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 t

13、hen max:=sum;exit end;try(x+1,y,dep+1,sum+ax+1,y);try(x+1,y+1,dep+1,sum+ax+1,y+1);end;beginreadln(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阶段

14、(起始点)各决策点至第n行的最佳路径。设：fi,j为从第i阶段中的点j至第n行的最大的数字和；则:fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=j=i.f1,1即为所求。,const maxn=100;varn,i,j:integer;a:array1.maxn,1.maxn of integer;f:array1.maxn,1.maxn of integer;begin readln(n);for i:=1 to n do for j:=1 to i do read（ai,j);for i:=1 to n do fn,i:=an,i;

15、for i:=n-1 downto 1 do for j:=1 to i do if fi+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,1;f i，j=max ai,j+fi-1,j-1,ai

16、,j+fi-1,j 2=j=imax(fn,1,fn,2,.,fn,n即为所求。,const maxn=100;var n,i,j:integer;a:array1.maxn,1.maxn of integer;f:array1.maxn,1.maxn of integer;maxsum:integer;begin readln(n);for i:=1 to n do for j:=1 to i do read(ai,j);fillchar(f,sizeof(f),0);f1,1:=a1,1;for i:=2 to n do begin fi,1:=ai,1+fi-1,1;for j:=2 t

17、o i do if fi-1,j-1fi-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(i2)a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不

18、下降序列，同时也有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 j:=i+1 to n do if(aimax)then begin max:=bj;p:=j end;if p0 then

19、 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,i,ans,j,k,m:longint;a,b:array1.10000 of longint;begin read(n);for i:=1 to n do read(ai)

20、;ans:=0;for i:=1 to n do begin j:=1;k:=ans;while j ans then inc(ans);bj:=ai;end;writeln(ans);end.,同样的道理我们也可以做最长不上升子序列等等最长XX子序列,3.背包问题,1.部分背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，.,Wn,它们的总价值分别为C1,C2,.,Cn.求旅行者能获得最大总价值。解决问题的方法是贪心算法:将C1/W1,C2/W2,.Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.,2.0/1背包 一个旅

21、行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。分析说明:显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).程序简单,但是当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

22、;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(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:=

23、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.,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.采药,辰辰是个天资聪颖

24、的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？,4.采药,【输入文件】输入文件medic.in的第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两

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

26、超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第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）为希望购买物品的个

27、数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格(v=10000)，p表示该物品的重要度(15)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900,6.金明的预算方案,金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”

28、。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件 附件电脑 打印机，扫描仪书柜 图书书桌 台灯，文具工作椅 无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要

29、度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。,6.金明的预算方案,【输入文件】输入文件的第1行，为两个正整数，用一个空格隔开：N m 其中N（0，表示该物品为附件，q是所属主件的编号）【输出文件】输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。,6.金明的预算方案,【输入样例】1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【输出样例】2200,转化为01背包问题考虑到每个主件最多只有两

30、个附件，因此我们可以通过转化，把原问题转化为01背包问题来解决，在用01背包之前我们需要对输入数据进行处理，把每一种物品归类，即：把每一个主件和它的附件看作一类物品。处理好之后，我们就可以使用01背包算法了。在取某件物品时，我们只需要从以下四种方案中取最大的那种方案：只取主件、取主件附件1、取主件附件2、既主件附件1附件2。很容易得到如下状态转移方程：fi,j=maxfi-1,j，fi-1,j-ai,0+ai,0*bi,0，fi-1,j-ai,0-ai,1+ai,0*bi,0+ai,1*bi,1，fi-1,j-ai,0-ai,2+ai,0*bi,0+ai,2*bi,2，fi-1,j-ai,0-

31、ai,1-ai,2+ai,0*bi,0+ai,1*bi,1+ai,2*bi,2 其中，fi,j表示用j元钱，买前i类物品，所得的最大值，ai,0表示第i类物品主件的价格，ai,1表示第i类物品第1个附件的价格，ai,2表示第i类物品第2个附件的价格，bi,0,bi,1,bi,2分别表示主件、第1个附件和第2个附件的重要度。fi-1,j表示把j元钱全部投入前i-1类物品所得的最大值，即不取第i类物品这一方案，fi-1,j-ai,0+ai,0*bi,0表示只取第i类物品的主件这一方案，fi-1,j-ai,0-ai,1+ai,0*bi,0+ai,1*bi,1，表示取第i类物品的主件和第个附件这一方案

32、，fi-1,j-ai,0-ai,2+ai,0*bi,0+ai,2*bi,2，表示取第i类物品的主件和第2个附件这一方案，fi-1,j-ai,0-ai,1-ai,2+ai,0*bi,0+ai,1*bi,1+ai,2*bi,2，则表示取第i类物品的主件和两个附件这一方案。,var a:array1.60,0.3 of integer;/a数组用来存放每一类物品，ai,3用来保存每类物品主件的编号b:array1.60,0.2 of integer;f:array0.60,0.3200 of integer;n,m,i,s,v,p,q,j:integer;begin fillchar(a,sizeo

33、f(a),0);fillchar(b,sizeof(b),0);readln(n,m);n:=n div 10;s:=0;for i:=1 to m do begin readln(v,p,q);/读入数据 v:=v div 10;/优化，因为每个物品的价格是10的整数倍 if q=0 then begin/主件 inc(s);as,0:=v;as,3:=i;bs,0:=p;end else begin/是附件 for j:=1 to s do/此循环用来查找该附件的主件，找到后就退出循环 if aj,3=q then break;if aj,1=0 then begin aj,1:=v;bj

34、,1:=p;end else begin aj,2:=v;bj,2:=p;end;end;end;,fillchar(f,sizeof(f),0);m:=s;/处理完输入数据后，s为共有多少类物品 for i:=1 to m do/对m类物品进行动态规划，枚举物品 for j:=0 to n do/枚举状态 begin/找最优的方案 fi,j:=fi-1,j;/不取第i类物品 if(j=ai,0)and(fi,j=(ai,0+ai,1)and(fi,j=(ai,0+ai,2)and(fi,j=(ai,0+ai,1+ai,2)and(fi,jfi-1,j-ai,0-ai,1-ai,2+ai,0*

35、bi,0+ai,1*bi,1+ai,2*bi,2)then fi,j:=fi-1,j-ai,0-ai,1-ai,2+ai,0*bi,0+ai,1*bi,1+ai,2*bi,2;end;writeln(fm,n*10);end.,7.最长公共子序列,最长公共子序列：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=x0，x1，.，xm-1，序列Y=y0，y1，.，yk-1是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，.，k-1，有xij=yj。例如，X=ABCBDAB，Y=BCDB是X的一个子序

36、列。给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。,我们以ACDEFACDE与CCACDEFCD两个序列为例，研究求最长公共子序列的做法。,不难发现，最长公共子序列与斜线的关系有关。我们要将上图的5连斜线与2连斜线接上！,d0,0:=0;for i:=1 to n do di,0:=0;for j:=1 to m do d0,j:=0;/初始化 for i:=1 to n do for j:=1 to m do if s1i=s2j then di,j:=di-1,j-1+1 else begin if di-1,jdi,

37、j-1 then di,j:=di-1,j else di,j:=di,j-1;end;,下面我们给出一个基本的程序段,8.回文词,【题目描述】（vijos1327）回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。,【输入格式】第一行包含一个整数N，表示给定字符串的长度，3=N

38、=5000 第二行是一个长度为N的字符串，字符串由大小写字母和数字构成。【输出格式】一个整数，表示需要插入的最少字符数。【样例输入】5 Ab3bd【样例输出】2,谁能够用刚刚我们讲到的最长公共子序列来解决这道题呢？,这道题看起来与最长公共子序列毫无关系，但是如果我们将字符串倒过来就会发现其中的精妙之处。在这里我们以样例 A b 3 b d为例S（原串）A b 3 b dS1（倒序串）d b 3 b ALCS b 3 b 我们实际需要添加的使其成为回文词的只有不在lcs中的A和d而已。下面谁能想到怎么写递推式？,vara,b:array1.1000of char;f:array0.1000,0.

39、1000of longint;n,i,j:integer;function max(x,y:longint):longint;beginif xy 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(n-fn,n);/输出需要配对的字符数 end

40、.,思考题：如果是3个字符串求最长公共子序列又该怎么做呢？,9.区间dp,合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个问题进行分解成两个或多个部分。特征：能将问题分解成为两两合并的形式求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。,10.整数划分,给出一个长度为n的数要在其中加m-1个乘号，分成m段这m段的乘积之和最大mn=20有T组数据，T=10000,10.整数划分,给出一个长度为n的数要在其中

41、加m-1个乘号，分成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,j=m 时间复杂度为Omn2,请大家想一想这道题的循环应该怎么写？,11.石子合并,【题目描述】在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

42、【输入格式】数据的第1行试正整数N,1N100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.【输出格式】输出共2行,第1行为最小得分,第2行为最大得分.【输入样例】4 4 4 5 9【输出样例】43 54,11.石子合并,这道题是不是和整数划分有很多相似之处，这也是一道区间dp题。但有一点非常不同，石子合并是在圆形操场，也就是说这不是一个线性的dp问题而是一个环形的dp问题，遇到这种题目我们又该如何去解决呢？,从这道题目来看，它是一个环形的结构，因此我们可以把这个环从某个点分开，然后扩展成为两倍，从而更加方便的枚举各个区间，解决了回环往复的问题，这个处理方法还应用在usaco1.1

43、 破碎的项链，还有能量项链的解题之中。,状态转移方程：fj,p:=maxfj,k+fk+1,p+sumj,p gj,p:=mingj,k+gk+1,p+sumj,p(其中的sum数组表示两点之间的和，包括两点)。,最后请问大家在变成两倍后我们解存在哪里？,我们只要找所有长度为n的区间内的最大值即可！,var f,g:array0.200,0.200 of longint;map:array0.200 of longint;n:longint;procedure init;var i:longint;begin fillchar(f,sizeof(f),0);filldword(g,sizeof

44、(g)2,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 exi

45、t(b);end;function min(a,b:longint):longint;begin if ab then exit(a)else exit(b);end;,procedure dp;var i,j,k,ans,p,ans1:longint;begin ans:=0;ans1:=maxlongint;for i:=1 to n do for j:=1 to 2*n-i-1 do begin p:=i+j;for k:=j to p-1 do begin fj,p:=max(fj,p,fj,k+fk+1,p+sum(j,p);gj,p:=min(gj,p,gj,k+gk+1,p+su

46、m(j,p);end;end;for i:=1 to n do begin if fi,i+n-1ans then ans:=fi,i+n-1;if gi,i+n-1ans1 then ans1:=gi,i+n-1;end;writeln(ans1);writeln(ans);end;,begin init;dp;end.,12.最大正方形,Na GG的院子是一个NN的网格，每颗杂草最多占据一个11的网格。由于时间紧迫，他已经来不及清理所有杂草，所以只希望能够找出一个最大的正方形区域，在这个区域内没有杂草。样例输入2-1000样例输出1,此类dp我们一般称之为坐标dp，如本题则是在一个二维坐标

47、系中找一个最大的正方形。这样的题如何写转移方程？,f(i,j)=minf(i-1,j-1),f(i-1,j),f(i,j-1)+1,为什么是这样？大家自己画图看一看!,解析：Gi+1j,Gij+1,Gi+1j+1分别为(i,j)向下、向右、向右下一格的状况。在(n-1,n-1)当且仅当三者都为1的时候，正方形才能扩充。从最右下向上，依次扩充即可。,13.能量项链,在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸

48、盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表

49、示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(41)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为(41)2)3）=10*2*3+10*3*5+10*5*10=710。,13.能量项链,输入格式输入文件的第一行是一个正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当1iN时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出格式输出文件只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。样例输入42 3 5 10样例输出710,13.能量项链,和前面那一道题有相似之处?,石子合并,动态转移方程 fi,j=maxfi,k+fk+1,j+pi*pk+1*pj+1(i=kj),谁能解释一下这个动态转移方程的意义,fi,k表示第i颗珠子到第k颗珠子此前释放的能量pi*pk+1*pj+1即为本次合并释放的能量同样，这也是一个环形的题目，所以我们和之前一样，将数组扩大一倍，最后选取长度为n且释放能量最大的为答案,