第25讲动态规划优秀课件.ppt

《第25讲动态规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《第25讲动态规划优秀课件.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2525讲动态规划讲动态规划1第1页，本讲稿共96页回顾：回顾：数字三角形数字三角形机器人捡垃圾机器人捡垃圾最大连续子序列和最大连续子序列和最长递增子序列最长递增子序列背包问题。背包问题。2第2页，本讲稿共96页简单的背包问题(0-1背包)设有种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N=100,M1000.输入数据：第一行两个数：物品总数，背包载重量M；两个数用空格分隔；第二行N个数,为种物品重量Wi(1000)；两个数用空格分隔；第三行N个数,为N种物品价值Vi(1000);两个数用空格分隔；

2、输出数据：总价值；输入样例1：4 104 3 5 715 7 20 25输出样例1：35输入样例2：4 202 9 10 15 2 9 10 16 输出样例2：193第3页，本讲稿共96页0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0-10物物品品0-4编号1234容量4357价值15720254件物品 背包容量：10算法：设fi,j:从1到i件物品中选若取干件放到容量为j的背包中，获得的最大价值。目标是：fn,m4第4页，本讲稿

3、共96页用fi,j表示在第到第i件物品中装入重量为j的背包获得的最大价值fi,j=max fi-1,j ,fi-1,j-Wi+Vi (1=i=n,1=j=wi1)fi-1,j:不放第不放第i件物品获得的价值。件物品获得的价值。5第5页，本讲稿共96页主程序：主程序：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);for i:=for i:=1 1 to n do to n do for j:=1 to m dofor j:=1 to m do begin begin fi,j:=fi-1,j;fi,j:=fi-1,j;/不选择第不选择第i i件物

4、品件物品 if(j=wi)and(fi,j=wi)and(fi,jB2-C4-D3-E最短距离：13倒推法：10第10页，本讲稿共96页动态规划的术语：1、阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。阶段的划分一般根据时间和空间来划分的。2、状态：某一阶段的出发位置成为状态，通常一个阶段有多个状态。状态通常可以用一个或一组数来描述，称为状态变量。3、决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。描述决策的变量称决策变量

5、 4、策略和最优策略 所有阶段的决策有序组合构成一个策略。最优效果的策略叫最优策略。11第11页，本讲稿共96页fkx=minfk+1yi+d x,yi状态转移方程：由已求得的状态来求未知状态，递推关系式称为状态转移方程。Xy1y2yiEFx:x到终点的最短距离。目标是f1A倒推：12第12页，本讲稿共96页fkx=minfk-1yi+d yi,xFx:起点到x最短距离。目标是f5E顺推：Xy1y2yiA13第13页，本讲稿共96页结合题目看方程：顺推和倒推结合题目看方程：顺推和倒推14第14页，本讲稿共96页一般形式：U：状态；X：策略顺推：fUk=optfUk-1+LUk-1,Xk-1 （

6、LUk-1,Xk-1：状态Uk-1通过策略Xk-1到达状态Uk 的费用）初始fU1；结果：f(Un)15第15页，本讲稿共96页一般形式：U：状态；X：策略倒推：fUk=optfUk+1+LUk,Xk （LUk,Xk：状态Uk通过策略Xk到达状态Uk+1 的费用）初始fUn；结果：f(U1)16第16页，本讲稿共96页动态规划问题的特征动态规划问题的特征 :1 1、最优子结构、最优子结构 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。2 2、重叠子问题、重叠子问题 在解决整个问题时，要先解决其子

7、问题，要解决这些子问题，又要先解决他们的子子问题。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。17第17页，本讲稿共96页3 3、无后效性原则、无后效性原则 “已经求得的状态值，不受未求的那些状态的影响”。后面阶段的状态只受前面阶段的状态的影响。对于任意两个状态，只能单向的进行转移。某个状态一旦被求出，以后不再会发生变化（不受后面的影响）。要求的状态在空间或时间上是有序的。18第18

8、页，本讲稿共96页最优子结构、重叠子问题、无后效性阶段1阶段2阶段3阶段4阶段5AB1B2C1C2C3C4D1D2D3E53163843855634319第19页，本讲稿共96页有后效性:D1阶段1阶段2阶段3阶段4阶段5AB1B2C1C2C3C4D1D2D3E5316384385564325220第20页，本讲稿共96页拓扑图（有向无环图）拓扑图（有向无环图）无后效性无后效性21第21页，本讲稿共96页非拓扑图（可能有环）非拓扑图（可能有环）有后效性有后效性 a ab bc c？b bc ca a？abc5111122第22页，本讲稿共96页动态规划的条件：无后效性、最优子问题动态规划的条件

9、：无后效性、最优子问题无后效性、最优子问题是否能满足与 状态的表示、阶段的划分、状态的转移有关23第23页，本讲稿共96页 1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；记忆化搜索（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。设计动态规划法的步骤：24第24页，本讲稿共96页 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）.定量处理的过程也就是决策实施的过程.动态规划的关键：25第25页，本讲

10、稿共96页fUn=初始值；for kn-1 downto 1 do 枚举阶段 for U取遍所有状态 do 枚举状态 for X取遍所有决策 do 枚举决策 fUk=optfUk+1+LUk,Xk；/LUk,Xk：状态Uk通过策略Xk到达状态Uk+1的费用输出：fU1:目标动态规划的一般倒推格式为：26第26页，本讲稿共96页fUfU1 1=初始值；初始值；for kfor k2 to n do 2 to n do 枚举每一个阶段枚举每一个阶段 for Ufor U取遍所有状态取遍所有状态 dodo for X for X取遍所有决策取遍所有决策 dodo fUfUk k=optfU=optf

11、Uk-1k-1+LU+LUk-1k-1,X,Xk-1k-1；/LU /LUk-1k-1,X,Xk-1k-1：状态状态U Uk-1k-1通过策略通过策略X Xk-1k-1到达状态到达状态U Uk k 的费用的费用输出：输出：fUfUn n:目标目标动态规划的一般顺推格式为：27第27页，本讲稿共96页贪心算法采用“自顶向下”的方式使用最优子结构的：先做选择，在当时看起来是最优的选择（只顾眼前利益），然后再求解选择的那个子问题。“先选择，再求解子问题”dp：“先寻找子问题的解，然后做出选择”。7 3 8 8 1 0 2 7 4 44 5 2 6 5“贪心算法贪心算法“和dp很相似，它使用的问题也具

12、有最优子结构。显著区别：28第28页，本讲稿共96页二、动态规划举例29第29页，本讲稿共96页【问题描述问题描述】总公司拥有高效生产设备总公司拥有高效生产设备M M台，准备分给下属的台，准备分给下属的N N个公司。各分公司个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。若获得这些设备，可以为国家提供一定的盈利。问：问：如何分配这如何分配这M M台设备才能使国家得到的盈利最大？求出最大盈利值。台设备才能使国家得到的盈利最大？求出最大盈利值。其中其中M=150,N=100M=150,N=100。分配原则：每个公司有权获得任意数目的设备。分配原则：每个公司有权获得任意数目的设备，但总台数

13、不得超过总设备数，但总台数不得超过总设备数M M。【输入输入】第一行两个数，第一个数是分公司数第一行两个数，第一个数是分公司数N N，第二个数是设备台数，第二个数是设备台数M M。接下来是一个接下来是一个N*MN*M的矩阵的矩阵A A，Ai,jAi,j是第是第i i个公司分配个公司分配j j台机器所能获台机器所能获得的盈利。得的盈利。0=Ai,j=10000=Ai,j=1000【输出输出】最大盈利值。最大盈利值。、机器分配、机器分配30第30页，本讲稿共96页【样例输入样例输入】3 43 410 15 26 3010 15 26 3020 32 38 4320 32 38 4312 20 27

14、 3512 20 27 35【样例输出样例输出】545431第31页，本讲稿共96页fi,j:前i个(1.i)公司分配j台机器获得的最大盈利。求如下的数组：f1,1,f1,2,f1,m f2,1,f2,2,f2,m fn,1,fn,2,fn,m目标：fn,m分析：32第32页，本讲稿共96页1234110152630220323843312202735ai,j:第i个公司分j台机器的获利fi,j:前i个公司分配j台机器获得的最大盈利。0123400000010101526302020324248302032445433第33页，本讲稿共96页fi,j=maxfi-1,j-k+ai,k(1=i=

15、n,1=j=m,0=k=j)初始：初始：f1,i:=a1,i i:1m目标：目标：fn,m动态转移方程：34第34页，本讲稿共96页for i:=1 to m do f1,i:=a1,i;for i:=2 to n do for j:=1 to m do for k:=0 to j do fi,j:=max(fi,j,fi-1,j-k+ai,k);格式一：35第35页，本讲稿共96页for i:=1 to n do for j:=1 to m do for k:=0 to j do fi,j:=max(fi,j,fi-1,j-k+ai,k);格式二：36第36页，本讲稿共96页【问题描述】假设

16、你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从1至V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边。花束则可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果Ij，则花束I必须放在花束j左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花

17、瓶必须空置，每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示。、花店橱窗布置（、花店橱窗布置（IOI99IOI99）37第37页，本讲稿共96页花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最

18、大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只需输出其中一种摆放方式。假设条件（Asumption）1F100，其中F为花束的数量，花束编号从1至F。FV100，其中V是花瓶的数量。-50Aij50，其中Aij 是花束i在花瓶j中时的美学值。38第38页，本讲稿共96页【输入】第一行包含两个数：F、V。随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数。【输出】最大美学值。【样例输入】3 57 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20【样例输出】53样例说明：束花分别依次插在、号花瓶

19、内。39第39页，本讲稿共96页花 瓶12345花 束1、杜鹃花72323-2、秋海棠-282833-3、康乃馨-242453fi，j=前i束花放入前j个花瓶内的最大美学价值（花i不一定必须插在瓶j内)目标:fn,m花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020ai,jfi,j方法一40第40页，本讲稿共96页分析：分析：ai,j=ai,j=花花i i放入放入j j瓶的美学价值。瓶的美学价值。fifi，j=j=前前i i束花放入前束花放入前j j个花瓶内的最大美学价值（个花瓶内的最大美学价值（花花i i不一定必须插在瓶不一定必须

20、插在瓶j j内内）。）。计算计算fi,jfi,j有两种情况：有两种情况：1):1):花花i i放入第放入第j j个花瓶中：个花瓶中：fifi，j=fi-1,j-1+ai,jj=fi-1,j-1+ai,j 2):2):花花i i不放入第不放入第j j个花瓶中个花瓶中,只能放在前只能放在前j-1j-1个花瓶内：个花瓶内：fifi，j=fi,j-1j=fi,j-1动态转移方程：动态转移方程：fifi，j jmaxmaxfi-1,j-1+ai,jfi-1,j-1+ai,j，fi,j-1fi,j-1初始化：初始化：fi,i=a1,1+a2,2+ai,i;fi,i=a1,1+a2,2+ai,i;目标：目标

21、：fn,mfn,m41第41页，本讲稿共96页容易理解的方法：f1,1:=a1,1;for i:=2 to n do fi,i:=fi-1,i-1+ai,i;/求对角线 for i:=2 to m-(n-1)do f1,i:=max(f1,i-1,a1,i);/求第一行 for i:=2 to n do for j:=i+1 to m-(n-i)do fi,j:=max(fi,j-1,fi-1,j-1+ai,j);程序实现时要根据方程和问题的实际意义，主要边界情况花 瓶12345花 束1、杜鹃花72323-2、秋海棠-282833-3、康乃馨-24245342第42页，本讲稿共96页写法改进：

22、写法改进：fillchar(f,sizeof(f),0);/至少保证第0行全部为0for i:=1 to n do fi,i-1:=-5001;/对角线下斜线为无穷小for i:=1 to n do for j:=i to m-(n-i)do fi,j:=max(fi,j-1,fi-1,j-1+ai,j);43第43页，本讲稿共96页分析：ai,j表示第i束花插到第j个花瓶中的价值；fi,j表示第i束花插到第j个花瓶后，也就是说：第i束花插在第个花瓶，前i-1束花插在前-个花瓶内所获得的价值和的最大值。动态转移方程：fi,jmaxfi-1,k+ai,j (i-1=k=j-1)枚举第i-1束花所

23、在的花瓶k初始化：f0,0=0;fi,0=-(1=i=n)目标：maxfn,i (1=ifi,j then fi,j:=fi-1,k;inc(fi,j,ai,j);end;ans:=min;for i:=n to m do if fn,ians then ans:=fn,i;45第45页，本讲稿共96页输出方案：输出方案：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);fillchar(path,sizeof(path),0);fillchar(path,sizeof(path),0);for i:=1 to n do for i:=1 to n

24、 do for j:=i to m-(n-i)do for j:=i to m-(n-i)do begin begin fi,j:=min;fi,j:=min;for k:=i-1 to j-1 do for k:=i-1 to j-1 do if fi-1,kfi,j then if fi-1,kfi,j then begin fi,j:=fi-1,k;pathi,j:=k;end;begin fi,j:=fi-1,k;pathi,j:=k;end;inc(fi,j,ai,j);inc(fi,j,ai,j);end;end;ans:=min;ans:=min;for i:=n to m do

25、 for i:=n to m do if fn,ians then if fn,ians then begin ans:=fn,i;last:=i;end;begin ans:=fn,i;last:=i;end;46第46页，本讲稿共96页dfs(n,last)dfs(n,last)procedure dfs(i,j:longint);procedure dfs(i,j:longint);begin begin if pathi,j0 then if pathi,j0 then begin begin dfs(i-1,pathi,j);dfs(i-1,pathi,j);write(j,);wr

26、ite(j,);end end else write(j,);else write(j,);end;end;47第47页，本讲稿共96页你刚刚继承了首珍贵的、没有发行的歌曲，它们由流行的演唱组录制。你的计划是选择其中一些歌曲来发行个唱片，每个唱片至多包含分钟的音乐，唱片中的歌曲之间不能重复。由于你是一个古典音乐的爱好者，所以你没办法区分这些歌曲的价值，你按照下面的标准作选择：1)这些唱片中的歌曲必须按它们写作的顺序排序。（如果第一个唱片录制了歌曲、，则第二个唱片只能从开始选择）2)包含歌曲的总数量尽可能的多。输入：第一行包含数值，（不大于的整数），下面包含首歌曲的长度，它们按写作的顺序排列，没

27、有一首歌曲超出唱片的长度，而且不可能将所有歌曲都放在唱片中。输出：输出应是按照标准进行选择个唱片，所能包含的最多歌曲数目。样例：输入：5 6 44 3 4 4 5输出：43、制作唱片48第48页，本讲稿共96页用ai保存第i首歌曲的长度。si,j用1张盘可以保存i到j首歌曲之间最多的歌曲数目。设fi,j=前i首歌用j张盘可以录制的最多数量。状态转移方程：fi,j=maxfk-1,j-1+sk,i (j=k=i)一部分是用j-1张盘把前k-1首歌能录制的最大数量，另一部分是用一张盘在第k到第i首歌之间能录制的数量。目标：fn,m算法一：49第49页，本讲稿共96页实现实现1 1：fillchar

28、(f,sizeof(f),0);fillchar(f,sizeof(f),0);for i:=1 to n do for i:=1 to n do for j:=1 to m do for j:=1 to m do for k:=1 to i do for k:=1 to i do fi,j:=max(fi,j,fk-1,j-1+sk,i);fi,j:=max(fi,j,fk-1,j-1+sk,i);时间：O(N2*M)50第50页，本讲稿共96页求求si,jsi,j readln(n,v,m);readln(n,v,m);for i:=1 to n do read(ai);for i:=1

29、to n do read(ai);for i:=1 to n do /for i:=1 to n do /起点起点i i begin begin num:=0;/i num:=0;/i到到j j能用一张盘刻的最多歌曲数量能用一张盘刻的最多歌曲数量 b0:=0;sum0:=0;b0:=0;sum0:=0;for j:=i to n do/for j:=i to n do/终点终点j j begin begin k:=num;k:=num;while ajbk do /while ajbk do /插入排序插入排序i i到到j j的歌曲的歌曲 begin bk+1:=bk;sumk+1:=sumk

30、+aj;dec(k);end;begin bk+1:=bk;sumk+1:=sumk+aj;dec(k);end;bk+1:=aj;sumk+1:=sumk+aj;bk+1:=aj;sumk+1:=sumk+aj;if sumnum+1=v then inc(num);if sumnum+1=v then inc(num);si,j:=num;si,j:=num;end;end;end;end;51第51页，本讲稿共96页时间：O(N3+N2*M)空间：N*Mfi,j与第j-1列有关52第52页，本讲稿共96页XXXXXXXXXXXXXXXXXXXX151011051153第53页，本讲稿共9

31、6页优化：减少状态和决策；按列优先求优化：减少状态和决策；按列优先求 fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);for j:=1 to m do for j:=1 to m do for i:=j to n-(m-j)do for i:=j to n-(m-j)do for k:=j to i do for k:=j to i do fi,j:=max(fi,j,fk-1,j-1+sk,i);fi,j:=max(fi,j,fk-1,j-1+sk,i);54第54页，本讲稿共96页算法2：fi,j,k:=max fi-1,j,k;/不刻录第i

32、首歌 fi-1,j,k-ai+1;/aik)and(j=1)目标：fn,m,0 或 fn,m-1,tfi,j,k:前i首歌，j张没用的光盘，另加一张光盘，有k分钟未使用。可以录制的歌曲的最大数量。55第55页，本讲稿共96页for i:=1 to n do for j:=0 to m do for k:=0 to t do begin fi,j,k:=fi-1,j,k;if(ai=k)and(fi,j,kk)and(j=1)and (fi,j,kfi-1,j-1,t-ai+1)then fi,j,k:=fi-1,j-1,t-ai+1;end;writeln(fn,m,0);时间：O(n*m*t

33、)空间：N*M*T56第56页，本讲稿共96页思考：最多能录制多长时间的歌曲？57第57页，本讲稿共96页某公司要出口一批货物，货物的种类是(50)，不同的货物用不同的集装箱装盛，它们的重量依次为a1,a2,an，（ai20），由运送带按a1,a2,an顺序依次运送到船边，现有m(10)艘船可共使用来运载这批货物，每条船的最大载重量w(100)，在装船时，按照传送带传送货物的顺序向船上搬运货物，由于传动带在传送过程中始终不停止，并且速度很快，一旦错过不选某件货物，就无法再搬到船上，如：第条船装了货物a1,a3，则第条船只能从a开始装，即a2被错过，无法再被装船。而且装船的规则是，只有一条船装完

34、后才能装下一条船。没有一件货物的重量超过船的载重量。编程：选择哪货物装到船上使这条船所能装载货物的最大重量（某件货物要么装要么不装）。输入：第一行：，m，w第二行：a1,a2,an输出：条船所能运载货物的最大重量。样例：输入：210输出：（选择 8 4 5）7、集装箱运输58第58页，本讲稿共96页提示：求货物的最大载重量，而不是求最多能装多少件货物！59第59页，本讲稿共96页算法一：fi,j,k:前i件货物，j条船，另加剩余容量为k的一条船能装的最大重量。fi,j,k:=max fi-1,j,k;/不装第i件货物 fi-1,j,k-ai+ai;/aik)and(j0)fn,m,0 或 fn

35、,m-1,w60第60页，本讲稿共96页for i:=1 to n dofor i:=1 to n do for j:=0 to m-1 do for j:=0 to m-1 do for k:=0 to w do for k:=0 to w do begin begin fi,j,k:=fi-1,j,k;fi,j,k:=fi-1,j,k;if k=ai then if k=ai then fi,j,k:=max(fi,j,k,fi-1,j,k-ai+ai);fi,j,k:=max(fi,j,k,fi-1,j,k-ai+ai);if(kai)and(j0)then if(kai)and(j0)

36、then fi,j,k:=max(fi,j,k,fi-1,j-1,w-ai+ai);fi,j,k:=max(fi,j,k,fi-1,j-1,w-ai+ai);end;end;时间：O(n*m*W)空间：N*M*W61第61页，本讲稿共96页分析：设fi,j:前i件货物用j条船的最大载重量。si,j:一条船在第i到第j件货物选择装的最大载重量 动态转移方程：fi,j=maxfk,j-1+sk+1,i (0=k=tx)and(dx,y=tx)and(dx,y=aj then if k=aj then dj,k:=max(dj,k,dj-1,k-aj+aj);dj,k:=max(dj,k,dj-1,

37、k-aj+aj);end;end;si,j:=dj,w;/si,j:=dj,w;/从从i i开始到开始到j j一条船的最大载重货物量一条船的最大载重货物量 end;end;end;end;求si,j方法2：时间:O(n2*w)65第65页，本讲稿共96页动态规划求解：for i:=1 to n do阶段 for j:=1 to m do状态 for k:=0 to i-1 do策略 fi,j:=max(fi,j,fk,j-1+sk+1,i);总时间：O(n2*w+n2*m)66第66页，本讲稿共96页8 8、最大、最大mm子段和问题子段和问题给定由n个整数（可能为负整数）组成的序列a1,a2,

38、.an，以及一个正整数m，要求确定序列a1,a2,.an的m个不相交子段，使这m个子段的总合达到最大。输入：第一行：N，m。n=1000,m=10 第二行：a1,a2,.an。中间一个空格。ai=(-30000,30000)输出：M个子段的最大和。样例输入：10 2-1 3 -1 4 -2 -3 5 -2 3 -1样例输出：1267第67页，本讲稿共96页分析：分析：m=1m=1的情况的情况令令FiFi：以：以aiai为终点（右边界）的子序列的最大和。为终点（右边界）的子序列的最大和。FI=maxak+ak+1+aI(1=k=I)FI=maxak+ak+1+aI(1=k=I)状态转移方程：状态

39、转移方程：fi=maxfi-1+ai,ai fi=maxfi-1+ai,ai：=maxfi-1,0+ai.=maxfi-1,0+ai.即看即看fifi的正负的正负初始：初始：f1=a1f1=a1目标：目标：maxfi 1=i=nmaxfi 1=i=n求最大连续子序列的和68第68页，本讲稿共96页算法算法1 1：令令fi,j:1fi,j:1到第到第i i数中，取数中，取j j段的最大和。段的最大和。fi,j=maxfk,j-1+dk+1,ifi,j=maxfk,j-1+dk+1,i (j-1=k=i-1)(j-1=k1m1的情况的情况69第69页，本讲稿共96页求求di,j:di,j:动规动规

40、for i:=1 to n dofor i:=1 to n do begin begin di,i:=ai;sum:=ai;max:=ai;di,i:=ai;sum:=ai;max:=ai;for j:=i+1 to n do for j:=i+1 to n do begin begin sum:=fmax(sum+aj,aj);sum:=fmax(sum+aj,aj);max:=fmax(max,sum);max:=fmax(max,sum);di,j:=max;di,j:=max;end;end;end;end;时间：O（N2）70第70页，本讲稿共96页求求fi,jfi,j f1,1:=

41、a1;for i:=2 to m do fi,i:=fi-1,i-1+ai;for j:=1 to m do for i:=j+1 to n do begin fi,j:=-maxlongint;for k:=j-1 to i-1 do fi,j:=fmax(fi,j,fk,j-1+dk+1,i);end;时间：O（N2*M）71第71页，本讲稿共96页算法算法2 2：令令fi,j:1fi,j:1到第到第i i数中，取数中，取j j段的最大和，段的最大和，并且第并且第j j个子段中包含个子段中包含aIaI。则目标是：则目标是：maxfI,m(m=I=n).maxfI,m(m=I=n).第第j

42、j段有两种情况：段有两种情况：第第j j段中只含有段中只含有aIaI一个数，即一个数，即aIaI独自一段：独自一段：fI,j=maxfk,j-1+aIfI,j=maxfk,j-1+aI（j-1=k=I-1j-1=k=I-1）；）；第第j j段中至少含段中至少含aI-1,aI-1,即即即即aIaI不是独自一段。不是独自一段。fI,j=fI-1,fI,j=fI-1,j j+aI+aI；fI,j=maxfI-1,j+aIfI,j=maxfI-1,j+aI，maxfk,j-1+aI maxfk,j-1+aI （j-1=k=I-1j-1=k=I-1）72第72页，本讲稿共96页f1,1:=a1;f1,1

43、:=a1;for i:=2 to m do fi,i:=fi-1,i-1+ai;for i:=2 to m do fi,i:=fi-1,i-1+ai;for j:=1 to m dofor j:=1 to m do for i:=j+1 to n do for i:=j+1 to n do begin begin fi,j:=fi-1,j+ai;fi,j:=fi-1,j+ai;for k:=j-1 to i-1 do for k:=j-1 to i-1 do fi,j:=fmax(fi,j,fk,j-1+ai);fi,j:=fmax(fi,j,fk,j-1+ai);end;end;ans:=-

44、maxlongint;ans:=-maxlongint;for i:=m to n do ans:=fmax(ans,fi,m);for i:=m to n do ans:=fmax(ans,fi,m);时间：O（N2*M）73第73页，本讲稿共96页有一个由数字0,1，2，.，9组成的数字串（长度不超过200），问如何将M(0=M=20)个加号(“+”)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+

45、46，算术表达式的值133。输入格式数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。输出格式所求得的最小和的精确值。输入输出举例输 入：82363983742 3输 出：2170 9、最小加法表达式74第74页，本讲稿共96页分析：S:string;输入的数串。n=length(s);m=加号的个数；设：fi,j=在数串s的前个字符中插个加号所得的最小值。目标：fn,m状态转移方程：fi,j=minfk,j-1+dk+1,i (j=k=i-1)di,j=数串s中第到第个字符组成的数值。前个字符中插个加号所得的最小值由两部分组成：一部分前个字符加j-1个加号

46、形成的最小值，另一部分第k+1到第i字符作为一个数。j=k1)do dec(k);while(di,j,k=0)and(k1)do dec(k);di,j,0:=k;di,j,0:=k;end;end;end;end;78第78页，本讲稿共96页大小比较大小比较 function fmin(a,b:data):data;function fmin(a,b:data):data;var i:integer;var i:integer;begin begin if a0b0 then exit(b);if a0b0 then exit(b);if a0b0 then exit(a);if a00

47、do while i0 do begin begin if aibi then exit(b);if aibi then exit(b);if aibi then exit(a);if ailen then len:=b0;if b0len then len:=b0;for i:=1 to len do ci:=ai+bi;for i:=1 to len do ci:=ai+bi;for i:=1 to len do for i:=1 to len do begin begin ci+1:=ci+1+ci div 10;ci+1:=ci+1+ci div 10;ci:=ci mod 10;ci

48、:=ci mod 10;end;end;if clen+10 then inc(len);if clen+10 then inc(len);c0:=len;c0:=len;fadd:=c;fadd:=c;end;end;80第80页，本讲稿共96页设设:fi,j:fi,j:合并第合并第i i到到j j堆的最小得分。堆的最小得分。datai,j:datai,j:第第i i到到j j堆石子的总数量。堆石子的总数量。则则:datai,j:=ai+ai+1+aj:datai,j:=ai+ai+1+aj动态转移方程动态转移方程:fi,j=min(fi,k+fk+1,j)+datai,jfi,j=min(

49、fi,k+fk+1,j)+datai,j i=k=j-1 i=k=j-1初始值：初始值：fi,i=0;fi,i=0;目标：目标：f1,nf1,n10、石子合并(线性)81第81页，本讲稿共96页数据范围的估计：DataI,j:最大20*100=2000，integer。FI,j:最大估计：需要2*n-1次合并，每次合并后的最大值不超过2000。N=100 （2*100-1）*2000=400000,longint即可。82第82页，本讲稿共96页求datai,j for i:=1 to n do begin datai,i:=ai;for j:=i+1 to n do datai,j:=dat

50、ai,j-1+aj;end;时间复杂度:n283第83页，本讲稿共96页 for i:=1 to n do fi,i:=0;初始化 for p:=1 to n-1 do 枚举阶段：距离p=j-i for i:=1 to n-p do 枚举状态：i begin j:=i+p;fi,j:=maxlongint;for k:=i to j-1 do 枚举决策 fi,j:=min(fi,j,fi,k+fk+1,j);fi,j:=fi,j+datai,j;end;时间:O(N3)动规求解过程：84第84页，本讲稿共96页Datai,j方法2：for i:=1 to n do read(ai);for i