动态规划学习资料.doc

动态规划基本原理动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。要了解动态规划的概念，首先要知道什么是多阶段决策问题。一、多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.图4-1 带权有向多段图让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最短路径的长度(下面简称最短距离)。我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A点要到达D点必然要经过B1和B2中的一个，所以A到D的最短距离必然等于B1到D的最短距离加上5，或是B2到D的最短距离加上2。同样的，B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2，。我们设Gi为点i到点D的距离，显然GC1=4，GC2=3，GC3=5，根据上面的分析，有：GB1=minGC1+3，GC2+2=5，GB2=minGC2+7，GC3+4=9，再就有GA=minGB1+5，GB2+2=10，所以A到D的最短距离是10，最短路径是AB1C2D。二、动态规划的术语1阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。2状态状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。3无后效性我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。4决策一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。5策略由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k)与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k)表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。6最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短路径是AB1C2D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：AB1C2是A到C2的最短路径，B1C2D也是B1到D的最短路径事实正是如此，因此我们认为这个例子满足最优性原理的要求。三、动态规划例子例1：数字三角形【问题描述】图示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；【输入数据：】由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如下：573 88 1 02 7 4 44 5 2 6 5【输出数据：】把最大总和（整数）写入OUTPUT.TXT文件。上例为：30【分析：】只要对该题稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺序求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。设：k（k）从第阶段中的点k至三角形顶点有一条最佳路径， 该路径所经过的数字的总和最大，k（k）表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设k1阶段中某点k沿左斜线向下的点；k2阶段中某点k沿右斜线向下的点；k（k1）阶段中k1的数字；k（k2）阶段中k2的数字；因而可写出顺推动规方程k（k）k-1（k）k（k1），k-1（k）k（k2）0（0）；，即：FI,j=max( fi-1,j+dI,j,fi-1,j-1+dI,j)边界条件：f1,1=d1,1经过一次顺推，便可分别求出由顶至底个数的条路径，在这条路径所经过的个数字和中，最大值即为正确答案。【参考程序】Program P1;ConstMaxn = 100;TypeNode = Record Val, Tot : Integer 当前格数字; 从1,1到当前格的路径所经过的数字和 End;Var List : Array 1.Maxn, 1.Maxn of Node; 计算表 N, Max, 行数, 最大总和 I, J : Integer; 辅助变量 Procedure Init;Begin Readln( N); 读三角形行数 For i := 1 to N Do 读入三角形各格的数字 For j := 1 to i Do Read( Listi, j.Val);End;initProcedure Main;Begin List1, 1.Tot := List1, 1.Val; 从1,1位置开始往下顺推 For i := 2 to N Do For j := 1 to i Do Begin Listi, j.Tot := -1; 从1,1至i,j的数字和初始化 If (j 1) And (Listi - 1, j - 1.Tot + Listi, j.Val Listi, j.Tot) Then Listi, j.Tot := Listi - 1, j - 1.Tot + Listi, j.Val; 若从i-1,j-1选择右斜线向下会使1,1至i,j的数字和最 大,则决策该步 If (j i) And (Listi - 1, j.Tot + Listi, j.Val Listi, j.Tot) Then Listi, j.Tot := Listi - 1, j.Tot + Listi, j.Val 若从i-1,j选择左斜线向下会使1,1至i,j的数字和最大,则决策该步 End; forMax := 1; 1,1至底行各点的N条路径所经过的数字和中,选择最大的一个输出 For i := 2 to N Do If ListN, i.Tot ListN, Max.Tot ThenMax := i;Writeln(ListN, Max.Tot) 输出最大总和 End; mainBegin Init; 读入数字三角形 Main 求最大总和 End.main例2：最长不下降序列（HNOI97）【问题描述】设有整数序列b1,b2,b3,bm，若存在i1i2i3in，且bi1bi2bi3bin，则称 b1,b2,b3,bm中有长度为n的不下降序列bi1,bi2,bi3,bin。求序列b1,b2,b3,bm中所有长度(n)最大不下降子序列输入：整数序列输出：最大长度n和所有长度为n的序列个数Total【分析】此题分为两个部分：求最大不下降序列长度和序列个数。首先我们考虑求最大长度。设F(i)为前I个数中的最大不下降序列长度。由题意不难得知，要求F(i)，需要求得F(1)F(I-1)，然后选择一个最大的F(j) ( jbj )，那么前I个数中最大不下降序列便是前j个数中最大不下降序列后添加bi而得。可见此任务满足最优子结构，可以用动态规划解决。通过上面的分析可得状态转移方程如下： F(i)=maxF(j)+1(jI , bjbi) 边界为F(1)=1显然只需要求序列个数即可。很容易想到下面的方法： 设Total(I)为前I个数中最长不下降序列的个数。 那么，要求Total(i)，只需找到所有的Total(j)满足jI，bjbi且前j个数最大不下降序列长度为前I个数中最大不下降序列长度+1，并把他们累加起来。即 Total(i)=Total(j) (jI, bjbi, F(i)=F(j)-1) 在求所有的Total(i)(F(i)=max)的累加和即可。 但这样考虑有一个致命的错误，如 1 2 2 这样一个序列，最大不下降序列长度为2。但如果按上述方法计算序列1 2会算两次。因此，我们对算法进行改进： 对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中的I个数在原序列中的位置。可见，当求Total(i)时，当F(j)=F(j+1) , b(j)=b(j+1)且Order(j+1)bj)and(filen then len:=fi 记录最大值 end; for i:=1 to n do orderi:=i; for i:=1 to n do 排序 for j:=i+1 to n do if (bibj)or(bi=bj)and(fifj) then begin t:=bi;bi:=bj;bj:=t; t:=fi;fi:=fj;fj:=t; t:=orderi;orderi:=orderj;orderj:=t end; tot:=0; 计算序列个数 fillchar(total,sizeof(total),0); for i:=1 to n do begin if fi=1 then totali:=1 else for j:=i-1 downto 1 do if (fj=fi-1)and(bjbi)and(orderjorderi) then if (bj+1bj)or(fj+1fj)or(orderj+1=orderi) then inc(totali,totalj); if (fi=len)and(bibi+1) then 记录累加最终值 tot:=tot+totali end; end;Procedure out; 输出 begin assign(output,fout);rewrite(output); writeln(len); writeln(tot); close(output) end;Begin init; main; outEnd.例3：BUY LOW, BUY LOWER【问题描述】 “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单：日期 1 2 3 4 5 6 7 8 9 10 11 12价格 68 69 54 64 68 64 70 67 78 62 98 87最优秀的投资者可以购买最多4次股票，可行方案中的一种是： 日期 2 5 6 10价格 69 68 64 62【问题输入】第1行: N (1 = N = 5000)，股票发行天数第2行: N个数，是每天的股票价格。【问题输出】 输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(=231)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。【输入样例】 BUYLOW.IN1268 69 54 64 68 64 70 67 78 62 98 87 【输出样例】 BUYLOW.OUT4 2【问题分析】 问题的第一部分是要求输入数据串中的一个最长下降序列的长度，可使用动态规划的方法，具体做法是从序列的最后一个元素开始，依次求出以第i个元素为第一个元素时的最长下降序列的长度leni，显然lenn=1，leni=max(lenj+1)，其中ia5=2可得t4=1，由len5=1,len2=2且a2=3a5=2和len3=1,len2=2且a2=3a3=1可得t2=t5+t3=2，对应a2,a3和a2,a5两个不同的以a2起头的最长下降序列，最终由len4=2,len1=3且a1=5a4=4和len2=2,len1=3且a1=5a2=3可得t1=t4+t2=1+2=3，所以本例中最长下降序列总数为3，分别为5,4,2,5,3,2和5,3,1。对于有相同元素的序列来说，如序列a=(5,4,1,4,2)，其中有两个相同的元素4，前面的推导过程不变，最后一步推导受两个相同元素的影响，不能能简单相加，由于a2=a4=4，对于所有的以a4起头的最长下降序列，只要将a4改为a2即可得到同样长度的下降序列，所以t4中的统计的序列在t2中也统计在内了，当序列中有相同元素时，为避免重复计数，从后向前递推时当后面的元素遇到前面的相同元素时则不再向前推。程序中为了方便处理，在整个序列前设置了一个标致元素a0=maxlongint，将len0置为maxlen+1。【参考程序】Program p8_3(Input, Output)；const maxn=5000；var i,j,n,l,maxlen:longint； a,len,t:array 0.maxn of longint；begin assign(input,buylow.in)； reset(input)； assign(output,buylow.out)； rewrite(output)； readln(n)； for i:=1 to n do read(ai)； for i:=1 to n do leni:=1； for i:=n-1 downto 1 do for j:=i+1 to n do if (aj=leni) then leni:=lenj+1； maxlen:=1； for i:=1 to n do if lenimaxlen then maxlen:=leni； a0:=maxlongint； len0:=maxlen+1； for i:=0 to n do if leni=1 then ti:=1 else ti:=0； for l:=1 to maxlen do begin for i:=n downto 1 do if leni=l then begin j:=i-1； while (j=0) and (ajai) do begin if (ajai) and (lenj=l+1) then inc(tj,ti)； dec(j) end； end； end； writeln(maxlen, ,t0)； close(input)； close(output)；end.例4：01背包问题【问题描述】：有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即fiv表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi。 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-ci的背包中”，此时能获得的最大价值就是f i-1v-ci再加上通过放入第i件物品获得的价值wi。注意fiv有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是fN V，而是fN0.V的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项fiv-1，这样就可以保证fN V就是最后的答案。至于为什么这样就可以，由你自己来体会了。 优化空间复杂度：以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1.N，每次算出来二维数组fi0.V的所有值。那么，如果只用一个数组f 0.V，能不能保证第i次循环结束后fv中表示的就是我们定义的状态fiv呢？fiv是由fi-1v和fi-1v-ci两个子问题递推而来，能否保证在推fiv时（也即在第i次主循环中推fv时）能够得到fi-1v和fi-1v -ci的值呢？事实上，这要求在每次主循环中我们以v=V.0的顺序推fv，这样才能保证推fv时fv-ci保存的是状态fi -1v-ci的值。伪代码如下： for i=1.N for v=V.0 fv=maxfv,fv-ci+wi; 其中的fv=maxfv,fv-ci一句恰就相当于我们的转移方程fiv=maxfi-1v,fi- 1v-ci，因为现在的fv-ci就相当于原来的fi-1v-ci。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了fiv由fiv-ci推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 总结：01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。例5：采药（NOIP2005初中组第3题）【问题描述】 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？【输入文件】 输入文件medic.in的第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】 输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】70 371 10069 11 2【样例输出】3【数据规模】对于30%的数据，M = 10；对于全部的数据，M =0;例6：花店橱窗布置【问题描述】 假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果IJ，则令花束I必须放在花束J左边的花瓶中。 例如，假设一束杜鹃花的标识数为1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如表8_1所示。表8_1花 瓶12345花束1 (杜鹃花)723-5-24162 (秋海棠)521-410233 (康乃馨)-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受，但你只要输出任意一种摆放方式。假设条件:1F100，其中F为花束的数量，花束编号从1至F。FV100，其中V是花瓶的数量。-50Aij50，其中Aij是花束i在花瓶j中的美学值。【问题输入】 输入文件名flower.inp，第一行包含两个数：F，V。随后的F行中，每行包含V个整数，Aij 即为输入文件中第（i+1 ）行中的第j个数。【问题输出】 输出文件名为flower.out，文件应包含两行：第一行是程序所产生摆放方式的美学值。第二行必须用F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。【输入样例】 flower.inp3 5 7 23 5 24 165 21 -4 10 23-21 5 -4 -20 20 【输出样例】 flower.out532 4 5【问题分析】 本题虽然是本届IOI中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？方法1：以花束的数目来划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量sk表示第k束花所在的花瓶。而对于每一个状态sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数fk(sk)表示前k束花，其中第k束插在第sk个花瓶中，所能取得的最大美学值。状态转移方程为：规划方程为（其中A(i,j)是花束i插在花瓶j中的美学值）边界条件 （V是花瓶总数，事实上这是一个虚拟的边界）方法2：以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量sk表示前k个花瓶中放了多少花。而对于任意一个状态sk，决策就是第sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(sk)表示前k个花瓶中插了sk束花，所能取得的最大美学值。状态转移方程为：规划方程为边界条件为两种划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了问题。只不过因为决策的选择有多有少，所以算法的时间复杂度也就不同。这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。【参考程序】Program p8_5(Input, Output)；varF,V:byte； 花束和花瓶的数目A:array 1.100,1.100 of shortint； Ai,j花束i放在花瓶j中的美学值Best:array 0.100,0.100 of integer；Besti,j前i束花放在前j个花瓶中的最优解Previous:array 1.100,1.100 of byte；Previousi,j在Besti,j的最优解中，花束i-1的位置procedure ReadIn； 读入vari,j:byte；beginreset(input)；readln(F,V)；for i:=1 to F dobeginfor j:=1 to V doread(Ai,j)；readln；end；close(input)；end；procedure Work； 规划主过程vari,j,t:byte；beginfillchar(Best0,sizeof(Best0),0)； 边界条件for i:=1 to F dofor j:=i to V+i-F dobeginBesti,j:=low(Besti,j)；for t:=i-1 to j-1 do枚举花束i-1的位置if Besti-1,tBesti,j thenbegin更新当前最优解Besti,j:=Besti-1,t；Previousi,j:=t；end；inc(Besti,j,Ai,j)；end；end；procedure Print；打印最优解vari,j:byte；Put:array 1.100 of byte；begini:=F；for j:=F+1 to V do选择全局最优解if BestF,jBestF,i theni:=j； i最后一束花的位置rewrite(output)；writeln(BestF,i)；for j:=F downto 1 dobeginPutj:=i；i:=Previousj,i； end； write(Put1)；for i:=2 to F dowrite( ,Puti)；writeln；close(output)；end；begin mainassign(input,flower.inp)；assign(output,flower.out)；ReadIn；Work；Print；end.例7：石子合并（NOI95）【问题描述】4459在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分. 编一程序,由文件读入堆数N及每堆石子数(20), (1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大 445989513922 总得分=8+13+22=434459441441822 总得分=14+18+22=54【输入数据:】 文件名由键盘输入,该文件内容为: 第一行为石子堆数N; 第二行为每堆石子数,每两个数之间用一空格分隔.【输出数据 :】 输出文件名为OUTPUT.TXT 从第1至第N行为得分最小的合并方案. 第N+1行为空行.从N+2到2N+1行是得分最大的合并方案. 每种合并方案用N行表示,其中第i行(1iN)表示第i次合并前各堆的石子数(依顺时钟次序输出,哪 一堆先输出均可). 要求将待合并的两堆石子数以相应的负数表示,以便识别,参见MODEL2.TXT 参考输入文件EXAMPLE2.TXT44 5 9 4参考输出文件MODEL2.TXT-4 5 9 -4-8 -5 9-9 -13-224 -5 -9 44 -14 -4-4 18-22【分析】看到本题，容易想到使用贪心法，即每次选取相邻最大或最小的两堆石子合并。然而这样做对不对呢？看一个例子。N=5 石子数分别为3 4 6 5 4 2。用贪心法的合并过程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24总分：61显然，贪心法是错误的。为什么？显然，贪心只能导致局部的最优，而局部最优并不导致全局最优。仔细分析后，我们发现此题可用动态规划进行解决。我们用dataI,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值，maxi,j表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：maxI,j = max(maxi, k + maxi + k, j k + dataI,k + dataI + k, j k) (2=k=j)maxi,1 = 0同样的，我们用mini,j表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：minI,j = min(mini, k + mini + k, j k + dataI,k + dataI + k, j k) (0=k=j)minI,0 = 0这样，我们完美地解决了这道题。空间复杂度为O(n2), 时间复杂度也是O(n2)。例8：凸多边形三角划分（HNOI97）【问题描述】给定一个具