动态规划经典题(C版)

第九章动态规划第一节动态规划的基本模型第二节动态规划与递推第三节背包问题第四节动态规划经典题

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。第四节动态规划经典题【例9-18】、合并石子【问题描述】在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。【编程任务】试设计一个程序，计算出将Ｎ堆石子合并成一堆的最小得分。【输入格式】第一行为一个正整数N(2≤Ｎ≤100)；以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。【输出格式】为一个正整数，即最小得分。s[i]表示前i堆石头的价值总和，f[i][j]表示把第i堆到第j堆的石头合并成一堆的最优值。

for(i=n-1;i>=1;i--)for(j=i+1;j<=n;j++)for(k=i;k<=j-1;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);输出f[1][n]【输入样例】713781621418【输出样例】239【参考程序】#include<cstdio>#include<cstring>intmin(inta,intb){returna>b?b:a;//三目运算符，相当于if(a>b)returnb;elsereturna;}intf[101][101];ints[101];intn,i,j,k,x;intmain(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);s[i]=s[i-1]+x;}memset(f,127/3,sizeof(f));//赋值127是很大的正数，若无/3后面的相加

for(i=1;i<=n;i++)f[i][i]=0;//可能超出int的范围

for(i=n-1;i>=1;i--)for(j=i+1;j<=n;j++)for(k=i;k<=j-1;k++)

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);

printf("%d\n",f[1][n]);return0;}【例9-19】乘积最大【问题描述】

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：1）3*12=362）31*2=62

这时，符合题目要求的结果是：31*2=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。【输入格式】mul.in

第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）第二行是一个长度为N的数字串。【输出格式】mul.out

输出所求得的最大乘积（一个自然数）。【输入样例】421231【输出样例】62【算法分析】

此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i][k]表示在前i位数中插入K个乘号所得的最大值，a[j][i]表示从第j位到第i位所组成的自然数。用f[i][k]存储阶段K的每一个状态，可以得状态转移方程：

f[i][k]=max{f[j][k-1]*a[j+1][i]}（k<=j<=i）边界值：

f[j][0]=a[1][j](1<j<=i)根据状态转移方程，我们就很容易写出动态规划程序：for(k=1;k<=r;k++)//r为乘号个数

for(i=k+1;i<=n;i++)for(j=k;j<i;j++)if(f[i][k]<f[j][k-1]*a[j+1][i])f[i][k]=f[j][k-1]*a[j+1][i]【参考程序】#include<cstdio>longlonga[11][11],f[11][11];longlongs;intn,i,k,k1,j;intmax(inta,intb){returna>b?a:b;}intmain(){scanf("%d%d",&n,&k1);scanf("%lld",&s);for(i=n;i>=1;i--){a[i][i]=s%10;s/=10;

}for(i=2;i<=n;i++)for(j=i-1;j>=1;j--)a[j][i]=a[j][i-1]*10+a[i][i];

for(i=1;i<=n;i++)//预处理不加乘号的情况

f[i][0]=a[1][i];for(k=1;k<=k1;k++)for(i=k+1;i<=n;i++)for(j=k;j<i;j++)

f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);

printf("%lld\n",f[n][k1]);

return0;}【例9-20】编辑距离【问题描述】设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：1、删除一个字符；2、插入一个字符；3、将一个字符改为另一个字符。【编程任务】对任的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。【输入格式】edit.in第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。【输出格式】edit.out只有一个正整数，为最少字符操作次数。【输入样例】sfdqxbwgfdgw【输出样例】4【算法分析】状态：f[i][j]记录ai与bj的最优编辑距离结果：f[m][n]，其中m、n分别是a、b的串长初值：b串空，要删a串长个字符；a串空，要插b串长个字符转移方程：当a[i]=b[j]时，f[i][j]=f[i-1][j-1]，否则，

f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1)说明：f[i-1][j-1]+1：改a[i]为b[j]；

f[i][j-1]+1：a[i]后插入b[j-1]；

f[i-1][j]+1：删a[i]。【参考程序】#include<cstdio>#include<cstring>intmin(inta,intb){returna<b?a:b;}intf[202][202];chars1[202],s2[202];inti,j,k,m,n;intmain(){scanf("%s%s",s1,s2);m=strlen(s1);n=strlen(s2);for(i=1;i<=m;i++)f[i][0]=i;//到i位置为止把字符串A的内容全部删除

for(i=1;i<=n;i++)f[0][i]=i;//在开头给字符串A添上和B到i位置相同的字符

for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1];elsef[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;

printf("%d\n",f[m][n]);return0;}【例9-21】方格取数【问题描述】

设有N×N的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：某人从图中的左上角的A出发，可以向下行走，也可以向右行走，直到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。【编程任务】此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。【输入格式】Pane.in输入文件Pane.in第一行为一个整数N（N≤10），表示N×N的方格图。接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。一行000表示结束。【输出格式】Pane.out输出文件Pane.out包含一个整数，表示两条路径上取得的最大的和。【输入样例】

823132663574414522156463157214000【输出样例】67【算法分析】一个四重循环枚举两条路分别走到的位置。由于每个点均从上或左继承而来，故内部有四个if，分别表示两个点从上上、上左、左上、左左继承来时，加上当前两个点所取得的最大值。a[i][j]表示(i,j)格上的值，sum[i][j][h][k]表示第一条路走到(i,j)，第二条路走到(h,k)时的最优解。例如，sum[i][j][h][k]=max{sum[i][j][h][k],sum[i-1][j][h-1][k]+a[i][j]+a[h][k]}，表示两点均从上面位置走来。当(i,j)<>(h,k)）时sum[i][j][h][k]:=max{sum[i-1][j][h-1][k],sum[i][j-1][h][k-1],sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]}+a[i][j]+a[h][k];当(i,j)=(h,k)时sum[i][j][h][k]:=max{sum[i-1][j][h-1][k],sum[i][j-1][h][k-1],sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]}+a[i][j];【参考程序1】#include<cstdio>intmax(inta,intb){returna>b?a:b;}inta[51][51];intsum[51][51][51][51];intn,i,j,h,k,x,y,z;intmain(){scanf("%d%d%d%d",&n,&x,&y,&z);while(x&&y&&z)//C++中大于0的正整数都看作true，只有0看作false{a[x][y]=z;

scanf("%d%d%d",&x,&y,&z);}for(i=1;i<=n;i++)

for(j=1;j<=n;j++)for(h=1;h<=n;h++)for(k=1;k<=n;k++){inttmp1=max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]);inttmp2=max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]);

sum[i][j][h][k]=max(tmp1,tmp2)+a[i][j];if(i!=h&&j!=k)sum[i][j][h][k]+=a[h][k];}printf("%d\n",sum[n][n][n][n]);

return0;}【例9-22】低价购买(buylow)【问题描述】“低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的购买建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单：日期123456789101112价格686954646864706778629887最优秀的投资者可以购买最多4次股票，可行方案中的一种是：日期25610价格69686462【输入格式】输入文件共两行，第1行:N(1<=N<=5000)，股票发行天数；第2行:N个数，是每天的股票价格。【输出格式】输出文件仅一行，包含两个数:最大购买次数和拥有最大购买次数的方案数(<=231)，当两种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。【输入样例】buylow.in12696854706864706778629887【输出样例】buylow.out44【算法分析1】先探索一下样例，最大购买次数为4次，共有4种方案，分别为69、68、64、62；69、68、67、62；70、68、64、62；70、68、67、62。我们发现，这道题实际上是在一个数列中选出一个序列，使得这个序列是一个下降序列（即序列中的任意一个数必须大于它后面的任何一个数），且要使这个序列的长度最长。但是这道题要输出总的方案数，这就需要对原有的求解过程做一些变动。求方案总数最主要的是要剔除重复方案。在样例中，第2和第5个数都是68。以第一个68结尾的最长下降序列的方案为69、68；以第二个68结尾的最长下降序列的方案为69、68和70、68——这时候就产生了方案的重复，即产生了两个69、68。显然后面的68要比前面一个更优，因为后面的68位置更靠后，以这个68结尾的最长下降序列的总数肯定要比前面一个多，而且其方案必定囊括了前面一个68的所有方案。因此，在解题过程中，我们就可以只考虑后面一个68。推广开来，如果当前状态之前存在重复的状态，我们只要考虑离当前状态位置最近的那一个即可。设F（i）表示到第i天，能够购买的最大次数，显然有：F（1）=1，F（i）=max{F(j)+1}(1<=j<=i-1,且OK[j]=true)，OK[j]=true表示相同价格时，该位置更优。【参考程序1】#include<cstdio>#include<cstring>boolok[50001];inta[5001],b[5001],f[5001];intn,i,j,k,max,num;intmain(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);

b[1]=1;f[1]=1;for(i=2;i<=n+1;i++){max=0;f[i]=1;for(j=i-1;j>=1;j--)if(a[i]<a[j])if(b[j]>max)//b[j]表示以第j天结尾的最大购买次数{max=b[j];memset(ok,1,sizeof(ok));

ok[a[j]]=false;f[i]=f[j];

}elseif(b[j]==max&&ok[a[j]])

{ok[a[j]]=false;f[i]+=f[j];

}b[i]=max+1;}printf("%d%d",b[n+1]-1,f[n+1]);return0;}【算法分析2】关于求第一问，很简单，求最长下降序列就行了，依次求出以第i个元素为最后一个元素时的最长下降序列的长度longest(i)，边界条件longest(1)=1，状态转移方程为：longest(i)=max{longest(j)+1},其中i>1，j=1,2…,i-1，且j同时要满足条件：序列中第j个元素大于第i个元素。关于第二问，就并非如此简单了，因为需要求出最大购买次数的方案数，并且方案“看起来”不能重复，即，购买价格序列是不能一样的。如何解决该问题，我们来看一个简单的例子，假如股票价格序列为:4、2、2、3、1，则购买方案有两种4、2、1和4、3、1其中4、2、1序列重复了，我们在求longest(i)时，longest(1)=1，longest(2)=2，longest(3)=2，longest(4)=2，那么我们求longest(5)时到底选用前边的那一组数据呢？显然，那一组都可以，这就使总方案数不唯一了，我们需要记录下来此时的方案数solution(5)，由于股价p(2)和p(3)相同，所以solution(2)和solution(3)只能有一个累加到solution(5)里，我们取solution值较大的累加到solution(5)里，如果solution(2)=solution(3)，则选solution(2)，所以solution(5)=solution(2)+solution(4)，由此我们可以写出状态转移方程:solution(i)=∑solution(j)，其中j满足：0<j<i，且longest(j)=longest(i)-1,且p(j)值不重复。为了便于计算，我们这里把i的取值扩大到n+1，p[n+1]=-1，我们要求的longest值即为longest[n+1]-1，solution值即为solution[n+1]，想一想这样处理有什么好处？为什么？【参考程序2】#include<cstdio>#include<cstring>constintmaxn=5002;structprice{intlongest,solution;}d[maxn];intp[maxn],t[maxn][2];intn,i,j,k,maxlong;intmain(){scanf("%d",&n);

for(i=1;i<=n;i++)scanf("%d",&p[i]);

p[n+1]=-1;d[1].longest=d[1].solution=1;

for(i=2;i<=n+1;i++){maxlong=0;for(j=1;j<i;j++)if(p[j]>p[i]&&d[j].longest>maxlong)maxlong=d[j].longest;d[i].longest=maxlong+1;d[i].solution=0;memset(t,0,sizeof(t));if(!maxlong)d[i].solution=1;else/*当d[j].longest等于d[i].longest-1，即等于maxlong，且p[j]>p[i]时，求出d[j].solution值并累加得到d[i].solution，其中股价相等时，取d[j].solution值大的累加入d[i].solution*/for(j=1;j<i;j++)if(d[j].longest==maxlong&&p[j]>p[i])

{k=1;while(t[k][0]!=p[j]&&t[k][0]!=0)k++;if(!t[k][0])/*当股价不相等时，直接累加入d[i].solution，并增加数组k的记录*/

{t[k][0]=p[j];t[k][1]=d[j].solution;d[i].solution+=d[j].solution;}else/*当股价有相等且d[j].solution值较大时，将两天的solution差值累加入d[i].solution，以达到取较大值累加的目的，并修改数组k的相应得记录*/

{if(t[k][1]<d[j].solution)

d[i].solution+=d[j].solution-t[k][1];t[k][1]=d[j].solution;}}}printf("%d%d\n",d[n+1].longest-1,d[n+1].solution);

return0;}【例9-23】最长公共子序列【问题描述】一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1,x2,…,xm>，则另一序列Z＝<z1，z2，…，zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有：

Xij=Zj例如，序列z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称z是序列x和Y的公共子序列。例如，若x＝<A,B,C,B,D,A,B>和Y＝<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的一个公共子序列,序列<B,C,B,A>也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列．因为x和Y没有长度大于4的公共子序列。给定两个序列X＝<x1，x2，…，xm>和Y=<y1,y2…．yn>．要求找出X和Y的一个最长公共子序列。【输入格式】输入文件共有两行。每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。【输出格式】输出文件第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数0。否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示)。若符合条件的最长公共子序列不止一个，只需输出其中任意的一个。【样例输入】LCS.INABCBDABBDCABA【样例输出】LCS.OUT4BCBA【问题分析】动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。1．最长公共子序列的结构解最长公共子序列问题时最容易想到的算法是穷举搜索法。即对X的每一个子序列。检查它是否也是Y的子序列。从而确定它是否为X和Y的公共子序列。并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列，X的一个子序列相应于下标序列｛1，2，…，m｝的一个子序列。因此，X共有2^m个不同子序列，从而穷举搜索法需要指数时间。事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：定理：LCS的最优子结构性质设序列X=<x1,x2,…，xm>和Y=<y1,y2,…，yn>的一个最长公共子序列Z=<z1,z2,…,zk>．则：若xm=yn则zk=xm=yn且Zk-1是Xm-1和Yn-1最长公共子序列：若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=<x1,x2，…,xm-1>．Yn-1=<y1,y2,…,yn-1>．Zk-1=<z1,z2,…，Zk-1>。证明：用反证法。若zk≠xm且xm=yn,则<z1,z2,….zk,xm>是X和Y的长度为k+1的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾，因此，必有zk=xm=yn，由此可知Zk-1是Xm-1和Yn-1的一个长度为k－1的公共子序列。若Xm-1和Yn-1有一个长度大于k-1的公共子序列W,则将xm加在其尾部将产生X和Y的一个长度大于k的公共子序列．此为矛盾。故Zk-1是Xm-1和Yn-1的一个最长公共子序列。由于zk≠xm,Z是Xm-1和Y的一个公共子序列：若Xm-1和Y有一个长度大于k的公共子序列W,则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的一个最长公共子序列。这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2．子问题重叠性质由最长公共子序列问题的最优子结构性质可知．要找出X＝<x1，x2．…,xm>和Y＝<y1，y2，…，yn>的最长公共子序列．可按以下方式递归地进行：当xm=yn时．找出xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题．即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质，例如．在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题．即计算Xm-1和Yn-1的最长公共子序列。我们来建立子问题的最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列，故c[i][j]=0。由定理可建立递归关系如下：3．计算最优值直接利用上式容易写出一个计算c[i][j]的递归算法．但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有O(m*n)个不同的子问题．因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1，x2，…,xm>和Y=<y1,y2,…,yn>作为输入。输出两个数组c[0..m][0..n]和b[1..m][1..n]。其中c[i][j]存储Xi与Yj的最长公共子序列的长度,b[i][j]记录指示c[i][j]的值是由哪一个子问题的解达到的．这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m][n]中。由于每个数组单元的计算耗时O(1)，算法LCS_LENGTH耗时O(mn)。4．构造最长公共子序列由算法LCSENGTH计算得到的数组b可用于快速构造序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最长公共子序列。首先从b[m][n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i][j]中遇到“↖”时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i][j]中遇到“↑”时．表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i][j]中遇到“←”时,表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。在本算法中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。【参考程序】//ex9_23#include<cstdio>#include<cstring>#include<string>usingnamespacestd;intmax(inta,intb){returna>b?a:b;}constintmaxlen=201;intc[maxlen][maxlen];intn,i,j,l1,l2;charx[maxlen],y[maxlen];stringz="";intmain(){scanf("%s%s",x,y);

l1=strlen(x);l2=strlen(y);

for(i=1;i<=l1;i++)for(j=1;j<=l2;j++)

if(x[i-1]==y[j-1])c[i][j]=c[i-1][j-1]+1;elsec[i][j]=max(c[i-1][j],c[i][j-1]);

printf("%d\n",c[l1][l2]);i=l1;j=l2;

while(i&&j)if(x[i-1]==y[j-1]){z=x[--i]+z;//string类重载了运算符“+”、“=”，可直接使用

j--;}elseif(c[i-1][j]>c[i][j-1])i--;elsej--;printf("%s\n",z.c_str());//string类应加.c_str()获得相应的字符串值

return0;}【例9-24】复制书稿(book.pas)【问题描述】

现在要把m本有顺序的书分给k个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。【输入格式】

第一行两个整数m，k；（k≤m≤500）第二行m个整数，第i个整数表示第i本书的页数。【输出格式】

共k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。【输入输出样例】book.in book.out93 67 89【问题分析】

本题可以用动态规划解决，设f(k,m)为前m本书交由k个人抄写，需要的最短时间，则状态转移方程为

f[k][m]=min{max{f[k-1][i],},i=1,2,…,m-1}

动态规划求出的仅仅是最优值，如果要输出具体方案，还需根据动态规划计算得到的最优值，做一个贪心设计。具体来说，设最优值为T，那么k个人，每个人抄写最多T页。从最后一本书开始按逆序将书分配给k人去抄写，从第k个人开始，如果他还能写，就给他；否则第k个人工作分配完毕，开始分配第k-1个人的工作；以后再是第k-2个、第k-3个、……直至第1个。一遍贪心结束后，具体的分配方案也就出来了。【参考程序】#include<iostream>#include<cstdio>#include<cstdlib>usingnamespacestd;intmax1(int,int);intprint(int,int);intx,y,i,j,m,n,k,t,l;inta[501],f[501][501],d[501];intmain(){cin>>m>>k;for(i=0;i<=500;i++)for(j=0;j<=500;j++)f[i][j]=10000000;for(j=1;j<=m;j++){cin>>a[j];//输入m本书的页数

d[j]=d[j-1]+a[j];//d[j]为前j本书总的页数

f[1][j]=d[j];//f[i][j]为一个人抄前j本书所需时间

}for(i=2;i<=k;i++)//f[k][m]为前m本书交由k个人抄写，需要的最短时间

for(j=1;j<=m;j++)

for(l=1;l<=j-1;l++)if(max1(f[i-1][l],d[j]-d[l])<f[i][j])f[i][j]=max1(f[i-1][l],d[j]-d[l]);}print(m,k);//从第k个开始分配抄写方案intmax1(intx,inty)//求x和y中最大值{if(x>y)returnx;elsereturny;}intprint(inti,intj)//递归输出抄写页数的方案{intt,x;if(j==0)return0;if(j==1)//第1个人抄写1到i本书

{cout<<1<<""<<i<<endl;return0;}t=i;x=a[i];while(x+a[t-1]<=f[k][m])//从最后一本书按逆序分配第j个人抄写，只要能写，就给他

{x+=a[t-1];t--;}print(t-1,j-1);//用递归过程给第j-1个人分配抄写方案，这时只有t-1书了

cout<<t<<""<<i<<endl;//递归返回时输出，因为递归过程是最后1个人先分配抄书}【例题9-25】橱窗布置（Flower）【问题描述】

假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I<J，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V≤100，－50≤AIJ≤50，其中Aij是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵(AIJ)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。┌───┬───┬───┬───┬───┬───┐

│

│花瓶1│花瓶2

│花瓶3│花瓶4

│花瓶5│

├───┼───┼───┼───┼───┼───┤

│杜鹃花│

7

│

23

│

-5

│

-24

│

16

│

├───┼───┼───┼───┼───┼───┤

│秋海棠│

5

│

21

│

-4

│

10

│

23

│

├───┼───┼───┼───┼───┼───┤

│康乃馨│

-21

│

5

│

-4

│

-20

│

20

│

└───┴───┴───┴───┴───┴───┘1、假设条件

1≤F≤100，其中F为花束的数量，花束编号从1至F。

F≤V≤100，其中V是花瓶的数量。

-50≤Aij≤50，其中Aij是花束i在花瓶j中的美学值。2、输入输入文件是flower.in。第一行包含两个数：F，V。随后的F行中，每行包含V个整数，Aij

即为输入文件中第（i+1）行中的第j个数。3、输出输出文件必须是名为flower.out的正文文件，文件应包含两行：第一行是程序所产生摆放方式的美学值。第二行必须用F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。【样例输入】35723–5–2416521-41023-215-4-2020【样例输出】53245【解法一】【算法分析】

问题实际就是给定F束花和V个花瓶，以及各束花放到不同花瓶中的美学值，要求你找出一种摆放的方案，使得在满足编号小的花放进编号小的花瓶中的条件下，美学值达到最大。将问题进行转化，找出问题的原型。首先，看一下上述题目的样例数据表格。将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行选且只选一个数(花瓶)；摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给定一个数字表格，要求编程计算从顶行至底行的一条路径，使得这条路径所经过的数字总和最大(要求每行选且仅选一个数字)。同时，路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的列数。看到经过转化后的问题，发现问题与“数学三角形”问题十分相似，数字三角形问题的题意是：给定一个数字三角形，要求编程计算从顶至底的一条路径，使得路径所经过的数字总和最大(要求每行选且仅选一个数字)。同时，路径中相邻两行的数字，必须保证下一行数字的列数与上一行数字的列数相等或者等于上一行数字的列数加1。上例中已经知道：数字三角形中的经过数字之和最大的最佳路径，路径的每个中间点到最底层的路径必然也是最优的，可以用动态规划方法求解，对于“花店橱窗布置”问题经过转化后，也可采取同样的方法得出本题同样符合最优性原理。因此，可以对此题采用动态规划的方法。【参考程序】#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){inta[101][101],b[101][101],c[101][101],d[101];//a[i][j]花束i放在花瓶j中的美学值

//b[i][j]前i束花放在前j个花瓶中的最优解

//c[i][j]在b[i][j]的最优解中，花束i-1的位置

intf,v,i,j,k,max;//f,v花束和花瓶的数目

cin>>f>>v;for(i=1;i<=f;i++)

for(j=1;j<=v;j++)cin>>a[i][j];memset(b,128,sizeof(b));//这样处理，可以保证每束花都放进花瓶

for(i=1;i<=v-f+1;i++)//初始化第1束花放在第i个花瓶的情况

b[1][i]=a[1][i];for(i=2;i<=f;i++)for(j=i;j<=v-f+i;j++)for(k=i-1;k<=j-1;k++)//枚举花束i-1的位置

if(b[i-1][k]+a[i][j]>b[i][j]){b[i][j]=b[i-1][k]+a[i][j];//更新当前最优解

c[i][j]=k;//前一个花束的位置为k}max=-2100000000;for(i=f;i<=v;i++)if(b[f][i]>max){max=b[f][i];//选择全局最优解

k=i;//k最后一束花的位置

}cout<<max<<endl;//打印最优解

for(i=1;i<=f;i++){d[i]=k;k=c[f-i+1][k];}for(i=f;i>=2;i--)

cout<<d[i]<<"";

cout<<d[1]<<endl;}

由此可看出，对于看似复杂的问题，通过转化就可变成简单的经典的动态规划问题。在问题原型的基础上，通过分析新问题与原问题的不同之处，修改状态转移方程，改变问题状态的描述和表示方式，就会降低问题规划和实现的难度，提高算法的效率。由此可见，动态规划问题中具体的规划方法将直接决定解决问题的难易程度和算法的时间与空间效率，而注意在具体的规划过程中的灵活性和技巧性将是动态规划方法提出的更高要求。【解法二】【算法分析】flower一题是IOI99第一天第一题，该题如用组合的方法处理，将会造成超时。正确的方法是用动态规划，考虑角度为一束一束地增加花束，假设用b[i][j]表示1～i束花放在1到j之间的花瓶中的最大美学值，其中i<=j，则b[i][j]=max(b[i-1][k-1]+A[i][k])，其中i<=k<=j，A[i][k]的含义参见题目。输出结果时，显然使得b[F][k]取得总的最大美观值的第一个k值就是第F束花应该摆放的花瓶位置，将总的最大美观值减去A[i][k]的值即得到前k-1束花放在前k-1个瓶中的最大美观值，依次使用同样的方法就可求出每一束花应该摆放的花瓶号。由于这一过程是倒推出来的，所以程序中用递归程序来实现。【参考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;voidprint(int,int);intmax(inta,intb){returna>b?a:b;}inta[101][101],b[101][101];intmain(){intf,v;cin>>f>>v;for(inti=1;i<=f;i++)for(intj=1;j<=v;j++)cin>>a[i][j];memset(b,128,sizeof(b));//初始化b数组

for(inti=0;i<101;i++)b[0][i]=0;//没有放花时，美学值为0。这也是初始化

for(inti=1;i<=f;i++)for(intj=i;j<=v-f+i;j++){for(intk=i;k<=j;k++)

b[i][j]=max(b[i][j],b[i-1][k-1]+a[i][k]);

}intc=-1000000;for(inti=f;i<=v;i++)if(b[f][i]>c)c=b[f][i];

cout<<c<<endl;print(f,c);}voidprint(inti,intj){intn;if(i>0){n=i;while(b[i][n]!=j){n++;}print(i-1,j-a[i][n]);cout<<n<<"";}}记忆化搜索的应用一般来说，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折中的办法就是记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有使用价值的。举一个例子：如下图所示是一个有向无环图，求从顶点1到顶点6的最长路径。（规定边的方向从左到右）

我们将从起点（顶点1）开始到某个顶点的最长路径作为状态，用一维数组opt记录。Opt[j]表示由起点到顶点j时的最长路径。显然，opt[1]=0，这是初始状态，即动态规划的边界条件。于是，我们很容易地写出状态转移方程式：opt[j]=max{opt[k]+a[k][j]}（k到j有一条长度为a[k][j]的边）。虽然有了完整的状态转移方程式，但是还是不知道动态规划的顺序。所以，还需要先进行一下拓扑排序，按照排序的顺序推下去，opt[6]就是问题的解。可以看出，动态规划相比搜索之所以高效，是因为它将所有的状态都保存了下来。当遇到重复子问题时，它不像搜索那样把这个状态的最优值再计算一遍，只要把那个状态的最优值调出来就可以了。例如，当计算opt[4]和opt[5]时，都用到了opt[3]的值。因为已经将它保存下来了，所以就没有必要再去搜索了。但是动态规划仍然是有缺点的。一个很突出的缺点就是要进行拓扑排序。这道题的拓扑关系是很简单的，但有些题的拓扑关系是很复杂的。对于这些题目，如果也进行拓扑排序，工作量非常大。遇到这种情况，我们可以用记忆化搜索的方法，避免拓扑排序。【例9-26】滑雪【问题描述】

小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：

12345 161718196 152425207 142322218 131211109

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为25-24-17-16-1（从25开始到1结束），当然25-24……2…1更长，事实上这是最长的一条。【输入格式】

输入的第一行为表示区域的二维数组的行数R和列数C（1≤R、C≤100）下面是R行，每行有C个数代表高度。【输出格式】

输出区域中最长的滑坡长度。[i-1,j]↓[i,j-1]→[i,j]←[i,j+1][i+1,j]↑【输入样例】ski.in5512345161718196152425207142322218131211109【输出样例】ski.out25【算法分析】

由于一个人可以从某个点滑向上下左右相邻四个点之一，如上图所示。当且仅当高度减小，对于任意一个点[i,j]，当它的高度小于与之相邻的四个点（[i-1,j],[i,j+1],[i+1,j],[i,j-1]）的高度时，这四个点可以滑向[i,j]，用f[i][j]表示到[i,j]为止的最大长度，则f[i][j]=max{f[i+a][j+b]}+1，其中坐标增量{(a,b)=[(1,0),(-1,0),(0,1),(0,-1)],0<i+a<=r，0<j+b<=c，High[i][j]<High[i+a][j+b]}。为了保证满足条件的f[i+a][j+b]在f[i][j]前算出，需要对高度排一次序，然后从大到小规划（高度）。最后再比较一下所有f[i][j]{0<i≤r,0<j≤c}，找出其中最长的一条路线。我们还可以用记忆化搜索的方法，它的优点是不需进行排序，按照行的顺序，利用递归逐点求出区域中到达此点的最长路径，每个点的最长路径只求一次。【参考程序】#include<iostream>#include<cstdio>usingnamespacestd;intdx[5]={0,-1,0,1,0},//x的坐标增量

dy[5]={0,0,1,0,-1};//y的坐标增量longr,c,i,j,p,t,ans;longm[101][101],f[101][101];intsearch(int,int);intmain(){cin>>r>>c;

ans=0;for(i=1;i<=r;i++)for(j=1;j<=c;j++)cin>>m[i][j];//读入每个点的高度

for(i=1;i<=r;i++)//按照行的顺序，利用递归逐点求出区域中到达此点的最长路径

for(j=1;j<=c;j++){t=search(i,j);f[i][j]=t;if(t>ans)ans=t;//寻找最大长度值

}cout<<ans<<endl;}

intsearch(intx,inty)//函数的作用是求到[x,y]点的最长路径{inti,t,tmp,nx,ny;

if(f[x][y]>0)//此点长度已经求出，不必进行进一步递归，保证每

{//一个点的最大长度只求一次，这是记忆化搜索的特点

return(f[x][y]);}t=1;for(i=1;i<=4;i++)//从四个方向上搜索能达到[x,y]的点

{nx=x+dx[i];//加上横、纵坐标

ny=y+dy[i];if((nx>=1)&&(nx<=r)&&(ny>=1)&&(ny<=c)&&(m[x][y]<m[nx][ny]))//边界限制

{//高度比较

tmp=search(nx,ny)+1;//递归进行记忆化搜索

if(tmp>t)t=tmp;}}f[x][y]=t;return(t);}【上机练习】1、防卫导弹(Catcher.pas)【问题描述】

一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：

1、它是该次测试中第一个被防卫导弹截击的导弹；

2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。【输入格式】

从当前目录下的文本文件“CATCHER.IN”读入数据。该文件的第一行是一个整数N(0<=N<=4000)，表示本次测试中，发射的进攻导弹数，以下N行每行各有一个整数hi(0<=hi<=32767)，表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。【输出格式】

答案输出到当前目录下的文本文件“CATCHER.OUT”中，该文件第一行是一个整数max，表示最多能截击的进攻导弹数，以下的max行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。【输入输出样例】输入文件：CATCHER.IN

输出文件：CATCHER.OUT3

225

136

323

2、拔河比赛(tug.pas)【问题描述】

一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近。【输入格式】

输入数据的第1行是一个n，表示参加拔河比赛的总人数，n<=100，接下来的n行表示第1到第n个人的体重，每个人的体重都是整数（1<=weight<=450）【输出格式】

输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。【输入样例】tug.in310090200【输出样例】tug.out1902003、求最短距离(distance.pas)【问题描述】小雨家住在小区里。她今年上小学一年级。每天她都要走路去车站，然后坐车去上学。小区被道路分成许多正方形的块，共N*M块。由于道路太多，她总是迷路。作为程序高手，你帮小雨计算一下从