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

Presentation on theme: "第九章 动态规划 第一节 动态规划的基本模型 第二节 背包问题 第三节 动态规划经典题."— Presentation transcript:

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

2 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

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

4 s[i]表示前i堆石头的价值总和，f[i][j]表示把第i堆到第j堆的石头合并成一堆的最优值。
【输入样例】 7 13 8 16 21 4 18 【输出样例】 239 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]

5 【参考程序】 #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;

6 【例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 1231 【输出样例】 62

7 【算法分析】 此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入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]

8 【参考程序】 #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("%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];

9 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]); return 0; }

10 【例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]。

11 【参考程序】 #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; }

12 【例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包含一个整数，表示两条路径上取得的最大的和。

13 【输入样例】 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 【输出样例】 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];

14 【参考程序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;

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

16 【问题分析】 本题可以用动态规划解决，设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个。一遍贪心结束后，具体的分配方案也就出来了。

17 【参考程序】 #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]= ; 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 (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]);

18 print(m,k); //从第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个人先分配抄书

19 【例题9-23】橱窗布置（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)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。

20 1≤F≤100，其中F为花束的数量，花束编号从1至F。 F≤V≤100，其中V是花瓶的数量。
┌───┬───┬───┬───┬───┬───┐ │       │花瓶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所在的花瓶的编号。

21 【样例输入】 3 5 7 23 –5 –24 16 【样例输出】 53 2 4 5

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

23 【参考程序】 #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 }

24 max= ; 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;

25 由此可看出，对于看似复杂的问题，通过转化就可变成简单的经典的动态规划问题。在问题原型的基础上，通过分析新问题与原问题的不同之处，修改状态转移方程，改变问题状态的描述和表示方式，就会降低问题规划和实现的难度，提高算法的效率。由此可见，动态规划问题中具体的规划方法将直接决定解决问题的难易程度和算法的时间与空间效率，而注意在具体的规划过程中的灵活性和技巧性将是动态规划方法提出的更高要求。 【解法二】 【算法分析】 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个瓶中的最大美观值，依次使用同样的方法就可求出每一束花应该摆放的花瓶号。由于这一过程是倒推出来的，所以程序中用递归程序来实现。

26 【参考程序】 #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 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]);

27 } int c= ; 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<<" ";

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

29 我们将从起点（顶点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]的值。因为已经将它保存下来了，所以就没有必要再去搜索了。 但是动态规划仍然是有缺点的。一个很突出的缺点就是要进行拓扑排序。这道题的拓扑关系是很简单的，但有些题的拓扑关系是很复杂的。对于这些题目，如果也进行拓扑排序，工作量非常大。遇到这种情况，我们可以用记忆化搜索的方法，避免拓扑排序。

30 【例9-24】滑雪 【问题描述】 小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子： 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为 （从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]↑

31 【输入样例】ski.in 【输出样例】ski.out 25 【算法分析】 由于一个人可以从某个点滑向上下左右相邻四个点之一，如上图所示。当且仅当高度减小，对于任意一个点[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}，找出其中最长的一条路线。我们还可以用记忆化搜索的方法，它的优点是不需进行排序，按照行的顺序，利用递归逐点求出区域中到达此点的最长路径，每个点的最长路径只求一次。

32 【参考程序】 #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++) //按照行的顺序，利用递归逐点求出区域中到达此点的最长路径 t=search(i,j); f[i][j]=t; if (t>ans) ans=t; //寻找最大长度值 } cout<<ans<<endl;

33 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);

34 【上机练习】 1、防卫导弹(Catcher.pas) 【问题描述】
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： 1、它是该次测试中第一个被防卫导弹截击的导弹； 2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。 【输入格式】 从当前目录下的文本文件“CATCHER.IN”读入数据。该文件的第一行是一个整数N(0<=N<=4000)，表示本次测试中，发射的进攻导弹数，以下N行每行各有一个整数hi(0<=hi<=32767)，表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。

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

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

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

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

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

40 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

41 7、潜水员 【问题描述】 潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？ 例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量： 如果潜水员需要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个气缸里的氧和氮的容量及汽缸重量。

42 【输出格式】 仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。 【输入样例】 5 60 5 【输出样例】 249

43 8、火车票 【问题描述】 从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于Ekaterinburg，终于Sverdlovsk。Ekaterinburg被标号为1，Sverdlovsk被标号为n。（n为整条线路上的站点数） 线路上的任意两个站点间的直达票价是由它们间的距离决定的，票价根据以下规则制定： X为两站的距离 价格 0<X<=L1 C1 L1<X<=L2 C2 L2<X<=L3 C3

44 如果两站的间距超过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。 【输出格式】 一个整数，表示从给定的一个站到给定的另一个站的最小花费。

45 【输入样例】 7 2 6 3 8 13 15 23 【输出样例】 70

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

47 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 3 1 3 7 8 3 4 【输出样例】HUNGER.OUT 5

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

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

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

51 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意味着马是白色。 【输出格式】 只输出一个单一的数字，代表系数总和可能达到的最小值。

52 【输入样例】stable.in //６匹马３个马棚 //第１匹马为黑马 1 //第３匹马为白马 【输出样例】stable.out //最小系数总和

53 14、滑雪(ski.pas) 【问题描述】 小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子： 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为 （从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]↑