tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

动态规划经典题


第九章 动态规划
第一节 动态规划的基本模型

第二节 动态规划与递推
第三节 背包问题

第四节 动态规划经典题

动态规划程序设计是对解最优化问题的一种途径、一种方法, 而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样, 具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序 设计往

往是针对一种最优化问题,由于各种问题的性质不同,确定 最优解的条件也互不相同,因而动态规划的设计方法对不同的问题, 有各具特色的解题方法,而不存在一种万能的动态规划算法,可以 解决各类最优化问题。因此读者在学习时,除了要对基本概念和方 法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建 立模型,用创造性的技巧去求解。我们也可以通过对若干有代表性 的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计 方法。

第四节 动态规划经典题
【例9-18】、合并石子 【问题描述】 ? 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。 规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数 记为该次合并的得分。 【编程任务】 ? 试设计一个程序,计算出将N堆石子合并成一堆的最小得分。 【输入格式】 ? 第一行为一个正整数N (2≤N≤100); ? 以下N行,每行一个正整数,小于10000,分别表示第i堆石子的个数 (1≤i≤N)。 【输出格式】 ? 为一个正整数,即最小得分。

【输入样例】 7 13 7 8 16 21 4 18

【输出样例】 239

? s[i]表示前i堆石头的价值总和,f[i][j]表示把第i堆到 ? ? ? ? ?

第j堆的石头合并成一堆的最优值。 for (i=n;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]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【参考程序】 #include<cstdio> #include<cstring> int min(int a,int b) { return a > b ? b:a; // 三目运算符,相当于if(a>b) return b; else return a; } int f[101][101]; int s[101]; int n,i,j,k,x; int main() { 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]); return 0; }

? 【例9-19】乘积最大 ? 【问题描述】 ? 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著

?
? ? ? ? ? ? ? ? ? ? ? ? ? ?

名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了 一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参 加。活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部 分,找出一种分法,使得这K+1个部分的乘积最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串:312, 当N=3,K=1时会有以下两种分法: 1)3*12=36 2)31*2=62 这时,符合题目要求的结果是:31*2=62。 现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。 【输入格式】mul.in 第一行共有2个自然数N,K(6≤N≤40,1≤K≤6) 第二行是一个长度为N的数字串。 【输出格式】mul.out 输出所求得的最大乘积(一个自然数)。 【输入样例】 【输出样例】 4 2 62 1231

? 【算法分析】 ? 此题满足动态规划法的求解标准,我们把它按插入的乘号

? ? ? ? ? ? ? ?

数来划分阶段,若插入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> long long a[11][11],f[11][11]; long long s; int n,i,k,k1,j; int max(int a, int b) { return a>b?a:b; } int main() { scanf("%d%d",&n,&k1); scanf("%I64d",&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("%I64d\n",f[n][k1]); return 0;

? }

【例9-20】编辑距离 【问题描述】 ? 设A和B是两个字符串。我们要用最少的字符操作次数,将字符串 A转换为字符串B。这里所说 的字符操作共有三种: ? 1、删除一个字符; ? 2、插入一个字符; ? 3、将一个字符改为另一个字符。 【编程任务】 ? 对任的两个字符串A和B,计算出将字符串A变换为字符串B所用的最少字符操作次数。 【输入格式】edit.in ? 第一行为字符串A;第二行为字符串B;字符串A和B的长度均小于200。 【输出格式】edit.out ? 只有一个正整数,为最少字符操作次数。 【输入样例】 ? sfdqxbw ? gfdgw 【输出样例】 ? 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> int min(int a,int b){return a<b?a:b;} int f[202][202]; char s1[202], s2[202]; int i,j,k,m,n; int main() { 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]; else f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1; printf("%d\n",f[m][n]); return 0; }

【例9-21 】方格取数 【问题描述】 ? 设有N×N的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则 放入数字0。如下图所示:

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

【输入样例】 8 2 3 13 266 357 4 4 14 5 2 21 564 6 3 15 7 2 14 000 【输出样例】 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[i1][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][j1][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][j1][h-1][k]}+a[i][j];
? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【参考程序1】 #include<cstdio> int max(int a,int b){return a>b?a:b;} int a[51][51]; int sum[51][51][51][51]; int n,i,j,h,k,x,y,z; int main() { 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++) { int tmp1=max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]); int tmp2=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]); return 0; }

【例9-22】低价购买(buylow) 【问题描述】 ? ―低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是 伟大的投资者,你必须遵循以下的购买建议:―低价购买;再低价购买”。 每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次 数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票 的次数。你将被给出一段时间内一支股票每天的出售价(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.in ? 12 ? 69 68 54 70 68 64 70 67 78 62 98 87 【输出样例】buylow.out ? 44 【算法分析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> bool ok[50001]; int a[5001],b[5001],f[5001]; int n,i,j,k,max,num; int main() { 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]; }

? else ? if(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]); ? return 0; ? }

【算法分析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> const int maxn=5002; struct price { int longest,solution; } d[maxn]; int p[maxn],t[maxn][2]; int n,i,j,k,maxlong; int main() { 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); return 0;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【例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.IN ? ABCBDAB ? BDCABA 【样例输出】LCS.OUT ? 4 ? BCBA

? 【问题分析】 ? 动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各 ? ?

?

? ? ?

? ? ? ?

个步骤来设计一个解此问题的有效算法。 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和Yn1有一个长度大于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=<xl,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> using namespace std; int max(int a,int b){return a>b?a:b;} const int maxlen=201; int c[maxlen][maxlen]; int n,i,j,l1,l2; char x[maxlen],y[maxlen]; string z=""; int main() { 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; else c[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--; ? } ? else ? if (c[i-1][j]>c[i][j-1]) i--; ? else j--; ? printf("%s\n",z.c_str()); //string类应加.c_str()获得相应的字符串值 ? return 0; ? }

【例9-24】复制书稿(book.pas) 【问题描述】 现在要把m本有顺序的书分给k个人复制(抄写),每一个人的抄写速度 都一样,一本书不允许给两个(或以上)的人抄写,分给每一个人的书,必 须是连续的,比如不能把第一、第三和第四本书给同一个人抄写。 现在请你设计一种方案,使得复制时间最短。复制时间为抄写页数最多 的人用去的时间。 【输入格式】 第一行两个整数m,k;(k≤m≤500) 第二行m个整数,第i个整数表示第i本书的页数。 【输出格式】 共k行,每行两个整数,第i行表示第i个人抄写的书的起始编号和终止编 号。k行的起始编号应该从小到大排列,如果有多解,则尽可能让前面的人 少抄写。 【输入输出样例】 book.in book.out 93 15 123456789 67 89

【问题分析】 本题可以用动态规划解决,设f(k,m)为前m本书交由k个人抄写,需要的最短 时间,则状态转移方程为 m f[k][m]=min{max{f[k-1][i], ?T j }, i=1, 2, …, m-1}
j ?i ?1

动态规划求出的仅仅是最优值,如果要输出具体方案,还需根据动态规划计 算得到的最优值,做一个贪心设计。具体来说,设最优值为T,那么k个人,每个 人抄写最多T页。从最后一本书开始按逆序将书分配给k人去抄写,从第k个人开 始,如果他还能写,就给他;否则第k个人工作分配完毕,开始分配第k-1个人的 工作;以后再是第k-2个、第k-3个、……直至第1个。一遍贪心结束后,具体的 分配方案也就出来了。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【参考程序】 #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int max1(int,int); int print(int,int); int x,y,i,j,m,n,k,t,l; int a[501],f[501][501],d[501]; int main() { 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])

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

print(m,k); system("pause");

//从第k个开始分配抄写方案

int max1(int x,int y) //求x和y中最大值 { if (x>y) return x; else return y; } int print(int i,int j) //递归输出抄写页数的方案 { int t,x; if (j==0) return 0; if (j==1) //第1个人抄写1到i本书 { cout<<1<<" "<<i<<endl; return 0; } 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、假设条件 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所在的花瓶 的编号。

┌───┬───┬───┬───┬───┬───┐ │ │花瓶1 │花瓶2 │花瓶3 │花瓶4 │花瓶5 ├───┼───┼───┼───┼───┼───┤ │杜鹃花│ 7 │ 23 │ -5 │ -24 │ 16 ├───┼───┼───┼───┼───┼───┤ │秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 ├───┼───┼───┼───┼───┼───┤ │康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 └───┴───┴───┴───┴───┴───┘

│ │ │



【样例输入】 35 7 23 –5 –24 16 5 21 -4 10 23 -21 5 -4 -20 20

【样例输出】 53 245

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

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

【参考程序】 #include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { int a[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的位置 int f,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; } 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; }

//选择全局最优解 //k最后一束花的位置

//打印最优解

由此可看出,对于看似复杂的问题,通过转化就可变成简单的经典的动 态规划问题。在问题原型的基础上,通过分析新问题与原问题的不同之处, 修改状态转移方程,改变问题状态的描述和表示方式,就会降低问题规划和 实现的难度,提高算法的效率。由此可见,动态规划问题中具体的规划方法 将直接决定解决问题的难易程度和算法的时间与空间效率,而注意在具体的 规划过程中的灵活性和技巧性将是动态规划方法提出的更高要求。 【解法二】 【算法分析】 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> using namespace std; void print(int,int); int max(int a,int b) { return a>b?a:b; } int a[101][101],b[101][101]; int main() { int f,v; cin>>f>>v; for (int i=1;i<=f;i++) for (int j=1;j<=v;j++) cin>>a[i][j]; memset(b,128,sizeof(b)); //初始化b数组 for (int i=0;i<101;i++) b[0][i]=0; //没有放花时,美学值为0。这也是初始化 for (int i=1;i<=f;i++) for (int j=i;j<=v-f+i;j++) { for (int k=i;k<=j;k++) b[i][j]=max(b[i][j],b[i-1][k-1]+a[i][k]);

} int c=-1000000; for (int i=f;i<=v;i++) if (b[f][i]>c) c=b[f][i]; cout<<c<<endl; print(f,c);

} void print(int i,int j) { int n; 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】滑雪 【问题描述】 小明喜欢滑雪,因为滑雪的确很刺激,可是为了获得速度,滑的区域必须向 下倾斜,当小明滑到坡底,不得不再次走上坡或等着直升机来载他,小明想知道 在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算,区域由一个二维 数组给出,数组的每个数字代表点的高度。下面是一个例子: 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小,在 上面的例子中,一条可行的滑坡为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.in 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 【输出样例】ski.out 25 【算法分析】 由于一个人可以从某个点滑向上下左右相邻四个点之一,如上图所示。当 且仅当高度减小,对于任意一个点[i,j],当它的高度小于与之相邻的四个点([i1,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> using namespace std; int dx[5]={0,-1,0,1,0}, //x的坐标增量 dy[5]={0,0,1,0,-1}; //y的坐标增量 long r,c,i,j,p,t,ans; long m[101][101],f[101][101]; int search(int,int); int main() { 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;

int search(int x,int y) //函数的作用是求到[x,y]点的最长路径 { int i,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.OUT

3
25 36 23

2
1 3

2、拔河比赛(tug.pas) 【问题描述】 一个学校举行拔河比赛,所有的人被分成了两组,每个人必须(且只能够) 在其中的一组,要求两个组的人数相差不能超过1,且两个组内的所有人体重 加起来尽可能地接近。 【输入格式】 输入数据的第1行是一个n,表示参加拔河比赛的总人数,n<=100,接下 来的n行表示第1到第n个人的体重,每个人的体重都是整数(1<=weight<=450) 【输出格式】 输出数据应该包含两个整数:分别是两个组的所有人的体重和,用一个空 格隔开。注意如果这两个数不相等,则请把小的放在前面输出。 【输入样例】tug.in 3 100 90 200 【输出样例】tug.out 190 200

3、求最短距离(distance.pas) 【问题描述】 小雨家住在小区里。她今年上小学一年级。每天她都要走路去车站,然后坐车去 上学。小区被道路分成许多正方形的块,共N*M块。由于道路太多,她总是迷路。 作为程序高手,你帮小雨计算一下从她家到达车站的最短距离。注意。一般情况 下,小区内的方块建有房屋,只能沿着附近的街道行走,有时方块表示公园,那 么就可以直接穿过。样例如下图所示。 【输入格式】 第一行是N和M(0〈N,M≤1000〉。注意,小雨家的坐标在方块(1,1)的西南角,车 站在方块(M,N)的东北角。每个方块边长100米。接下来一行是整数k,表示可以 对角线穿过的方块坐标。然后有k行,每行是一个坐标。车站小雨家 【输出格式】 输出从小雨家到车站的最短距离,四舍五入到整数(米)。 【输入样例】distance.in 32 3 11 32 12 【输出样例】distance.out 383

4、机器分配(assigned.pas) 【问题描述】 总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得 这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家 得到的盈利最大?求出最大盈利值。其中M≤15,N≤10。分配原则:每个公司 有权获得任意数目的设备,但总台数不超过设备数M。 输入数据文件格式为:第一行有两个数,第一个数是分公司数N,第二个 数是设备台数M。 接下来是一个N*M的矩阵,表明了第 I个公司分配 J台机器的盈利。 【输入样例】assigned.in 33 //3个分公司分3台机器 30 40 50 20 30 50 20 25 30 【输出样例】assigned.out 70 //最大盈利值为70 11 //第一分公司分1台 21 //第二分公司分1台 31 //第三分公司分1台

5、复制书稿(book.pas) 【问题描述】 现在要把m本有顺序的书分给k给人复制(抄写),每一个人的抄写速度 都一样,一本书不允许给两个(或以上)的人抄写,分给每一个人的书,必 须是连续的,比如不能把第一、第三、第四本书给同一个人抄写。 现在请你设计一种方案,使得复制时间最短。复制时间为抄写页数最多 的人用去的时间。 【输入格式】 第一行两个整数m,k;(k≤m≤500) 第二行m个整数,第i个整数表示第i本书的页数。 【输出格式】 共k行,每行两个整数,第i行表示第i个人抄写的书的起始编号和终止编 号。k行的起始编号应该从小到大排列,如果有多解,则尽可能让前面的人 少抄写。 【输入输出样例】 book.in book.out 93 15 123456789 67 89

6、投资问题(invest.pas) 【问题描述】 现在有m个可投资项目,有n万元的资金,其中m和n为小于100的自然数。 对第i(1≤i≤m)个项目投资j万元(1≤j≤n,且j为整数)可获得的回报为Q(i,j),请 你编一个程序,求解并输出最佳的投资方案(即获得回报总值最高的投资方案)。 【输入格式】 m n Q(1,0) Q(1,1)……Q(1,n) Q(2,0) Q(2,1)……Q(2,n) …… Q(m,0) Q(m,1)……Q(m,n) 【输出格式】 r(1) r(2) · · · · · ·r(m) P 其中r(i)(1≤i≤m)表示对第i个项目的投资万元数,P为总的投资回报值,保 留两位有效数字,任意两个数之间空一格。当存在多个并列的最佳投资方案时, 只要求输出其中之一即可。 【输入样例】invest.in 2 3 【输出样例】invest.out 0 1.1 1.3 1.9 1 2 3.6 0 2.1 2.5 2.6

7、潜水员 【问题描述】 潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸:一个为 氧气,一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有 一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需 要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少? 例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的 重量: 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号 气缸)。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。 【输入格式】 第一行有2整数t,a(1<=t<=21,1<=a<=79)。它们表示氧,氮各自需 要的量。 第二行为整数n (1<=n<=1000)表示气缸的个数。 此后的n行,每行包括ti,ai,wi(1<=ti<=21,1<=ai<=79,1<=wi<=800) 3整数。这些各自是:第i个气缸里的氧和氮的容量及汽缸重量。

【输出格式】 仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低 值。 【输入样例】 5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 【输出样例】 249

8、火车票 【问题描述】 从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近 似的表示为一条线段,火车站就是线段上的点。线路始于Ekaterinburg,终于 Sverdlovsk。Ekaterinburg被标号为1,Sverdlovsk被标号为n。(n为整条线路上 的站点数)

线路上的任意两个站点间的直达票价是由它们间的距离决定的,票价根据以 下规则制定: X为两站的距离 0<X<=L1 价格 C1

L1<X<=L2
L2<X<=L3

C2
C3

如果两站的间距超过L3,则无直达车票。所以有时可能有必要买多张票, 通过转车的方式,从一个站到达另一个站。 例如,在上面的图中,有7个站点。2号站点到6号站点的距离超过L3,不 能买直达票。存在若干种中转的方法,其中的一种是买两张票:先花费C2从2 号站到达3号站,然后花费C3从3号站到6号站,一种花费C2+C3。 你的任务是,找出一种最经济的中转方案。 【输入格式】 从文本文件railway.in中读入数据。 第一行 6个整数L1, L2, L3, C1, C2, C3(1<=L1<L2<L3<=10^9, 1<=C1<C2<C3<=10^9),中间用空格分隔。 第二行一个整数n(2<=n<=100),表示线路上的车站数。 第三行两个整数s和t,分别是起点和终点的编号。注意:s不一定小于t。 以下的n-1行,按据Ekaterinburg远近,每行描述了一个车站的位置。它包 含一个整数,表示该车站距Ekaterinburg的距离。 任意两个车站的距离不超过10^9,任意两个相邻的车站的距离不超过L3。 【输出格式】 一个整数,表示从给定的一个站到给定的另一个站的最小花费。

【输入样例】 3 6 8 20 30 40 7 26 3 7 8 13 15 23 【输出样例】 70

9、单词的划分 【问题描述】 有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析,需 要将它划分成若干个部分,每个部分称为一个单词。出于减少分析量的目的,我 们希望划分出的单词数越少越好。你就是来完成这一划分工作的。 【输入格式】 从文本文件word.in中读入数据。 第一行,一个字符串。(字符串的长度不超过100) 第二行一个整数n,表示单词的个数。(n<=100) 第3~n+2行,每行列出一个单词。 【输出格式】 一个整数,表示字符串可以被划分成的最少的单词数。 【输入样例】 realityour 5 real reality it your our 注:原字符串可拆成real+it+your或reality+our,由于 【输出样例】 reality+our仅为两个部分,因此最优解为2,另外注意,单 2 词列表中的每个单词都可以重复使用多次,也可以不用

10、饥饿的牛 【问题描述】 牛在饲料槽前排好了队。饲料槽依次用1到N(1<=N<=2000)编号。每天晚 上,一头幸运的牛根据约翰的规则,吃其中一些槽里的饲料。 约翰提供B个区间的清单。一个区间是一对整数start-end , 1<=start<=end<=N,表示一些连续的饲料槽,比如1-3,7-8,3-4等等。牛可以任 意选择区间,但是牛选择的区间不能有重叠。 当然,牛希望自己能够吃得越多越好。给出一些区间,帮助这只牛找一些 区间,使它能吃到最多的东西。 在上面的例子中,1-3和3-4是重叠的;聪明的牛选择{1-3,7-8},这样可 以吃到5个槽里的东西。 【输入格式】 第一行,整数B(1<=B<=1000) 第2到B+1行,每行两个整数,表示一个区间,较小的端点在前面。 【输出格式】 仅一个整数,表示最多能吃到多少个槽里的食物。 【输入样例】HUNGER.IN 【输出样例】HUNGER.OUT 3 5 13 78 34

11、护卫队(convoy.pas) 【问题描述】 护卫车队在一条单行的街道前排成一队,前面河上是一座单行的桥。因为 街道是一条单行道,所以任何车辆都不能超车。桥能承受一个给定的最大承载 量。为了控制桥上的交通,桥两边各站一个指挥员。护卫车队被分成几个组, 每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端,该端的指挥 员就用电话通知另一端的指挥员,这样下一组车队才能开始通过该桥。每辆车 的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在 同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用 该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护 卫车队通过该桥所需的最短时间值。 【输入格式】 输入文件第一行包含三个正整数(用空格隔开),第一个整数表示该桥所能 承受的最大载重量(用吨表示);第二个整数表示该桥的长度(用千米表示);第三 个整数表示该护卫队中车辆的总数(n<1000)。接下来的几行中,每行包含两个 正整数W和S(用空格隔开),W表示该车的重量(用吨表示),S表示该车过桥能达 到的最快速度(用千米/小时表示)。车子的重量和速度是按车子排队等候时的顺 序给出的。 【输出格式】 输出文件应该是一个实数,四舍五入精确到小数点后1位,表示整个护卫车 队通过该桥所需的最短时间(用分钟表示)。

【输入样例】CONVOY.IN 100 5 10 40 25 50 20 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70 【输出样例】CONVOY.OUT 75.0

12、乘法游戏 【问题描述】 乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个 移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不 允许拿第1张和最后1张牌。最后一次移动后,这里只剩下两张牌。 你的目标是使得分的和最小。 例如,如果数是10 1 50 20 5,依次拿1、20、50,总分是 10*1*50+50*20*5+10*50*5=8000 而拿50、20、1,总分是1*50*20+1*20*5+10*1*5=1150。 【输入文件】 输入文件mul.in的第一行包括牌数(3<=n<=100),第二行包括N个1-100的 整数,用空格分开。 【输出文件】 输出文件mul.out只有一个数字:最小得分 【样例输入】 6 10 1 50 50 20 5 【样例输出】 3650

13、马棚问题(stable.pas) 【问题描述】 每天,小明和他的马外出,然后他们一边跑一边玩耍。当他们结束的时 候,必须带所有的马返回马棚,小明有K个马棚。他把他的马排成一排然 后跟随它走向马棚,因为它们非常疲劳,小明不想让他的马做过多移动。 因此他想了一个方法:将马按照顺序放在马棚中,后面的马放的马棚的序 号不会大于前面的马放的马棚序号。而且,他不想他的K个马棚中任何一 个空置,也不想任何一匹马在外面。已知共有黑、白两种马,而且它们相 处的并不十分融洽。如果有I个白马和J个黑马在一个马棚中,那么这个马 棚的不愉快系数将是i*j。所有K个马棚的不愉快系数的和就是系数总和。 确定一种方法把n匹马放入k个马棚,使得系数总和最小。 【输入格式】 在第一行有两个数字:N(1〈=N〈=500〉和K(1〈=K〈=N〉。在接 下来N 行是N 个数。在这些行中的第I行代表队列中的第I匹马的颜色:1意 味着马是黑色,0意味着马是白色。 【输出格式】 只输出一个单一的数字,代表系数总和可能达到的最小值。

【输入样例】stable.in 6 3 //6匹马3个马棚 1 //第1匹马为黑马 1 0 //第3匹马为白马 1 0 1 【输出样例】stable.out 2 //最小系数总和

14、滑雪(ski.pas) 【问题描述】 小明喜欢滑雪,因为滑雪的确很刺激,可是为了获得速度,滑的区域必须向 下倾斜,当小明滑到坡底,不得不再次走上坡或等着直升机来载他,小明想知道 在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算,区域由一个二维 数组给出,数组的每个数字代表点的高度。下面是一个例子: 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小,在 上面的例子中,一条可行的滑坡为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]↑


推荐相关:

动态规划经典问题

动态规划经典问题_计算机软件及应用_IT/计算机_专业资料。动态规划经典问题 1、三角...【代码】 // // 例题 1 三角数字塔问题 // // #include <stdio.h> #...


动态规划总结经典题目(经典中的经典)

动态规划总结经典题目(经典中的经典)_计算机软件及应用_IT/计算机_专业资料。经典算法总结(acm为例) 动态规划总结——经典问题总结 本文着重讨论状态是如何表示,以及...


动态规划典型例题

动态规划典型例题_数学_高中教育_教育专区。初学者的必备题目 1、单调递增最长子序列描述求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf...


几个经典的动态规划问题

几个经典动态规划问题_计算机软件及应用_IT/计算机_专业资料。经典动态规划动态...由题意不难得知, 要求 F(i),需要求得 F(1)—F(I-1),然后选择一个最...


动态规划经典案例详解(背包问题)

但是动态规划并没有一个简单的模型可以套用,对于每个 不同的题目都有对应的不同规划思路, 我们只能通过对一些动态规划经典案例的学习来训练 自己的动态规划思维能力...


经典的动态规划入门练习题

经典动态规划入门练习题_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 经典动态规划入门练习题_工学_高等教育_教育专区。动态规划入门练习题 ...


动态规划题目

动态规划题目_销售/营销_经管营销_专业资料。动态规划经典题和部分题解机器分配 总公司拥有高效生产设备 M 台,准备分给下属的 N 个公司.各分公司若获得这些设备...


动态规划习题精讲

动态规划习题精讲_数学_高中教育_教育专区。信息学竞赛中的动态规划专题哈尔滨工业大学 周谷越 【关键字】 动态规划 动机 状态 典型题目 辅助方法 优化方法 【摘要...


动态规划训练题目

动态规划训练题目_管理学_高等教育_教育专区。动态规划题目 【引例1、上楼梯】...绝对经典搞笑照片67份文档 九妖笑话 2014年笑话大全之让你笑个够 儿童笑话大全...


动态规划习题

动态规划经典教程 45页 20财富值 动态规划题目 38页 2财富值 动态规划_各种类型题 102页 10财富值 动态规划 9页 免费如要投诉或提出意见建议,请到百度文库投...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com