第九章 动态规划第一节 动态规划的基本模型第二节 背包问题第三节 动态规划经典题动态规划程序设计是对解最优化问题的一种途径、一种方法， 而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样， 具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序 设计往往是针对一种最优化问题，由于各种问题的性质不同，确定 最优解的条件也互不相同，因而动态规划的设计方法对不同的问题 ，有各具特色的解题方法，而不存在一种万能的动态规划算法，可 以解决各类最优化问题。因此读者在学习时，除了要对基本概念和 方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去 建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表 性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设 计方法。第四三节 动态规划经典题【例9-18】、合并石子 【问题描述】 w在一个操场上一排地摆放着堆石子。现要将石子有次序地合并成一堆 。规定每次只能选相邻的堆石子合并成新的一堆，并将新的一堆石子 数记为该次合并的得分。 【编程任务】 w试设计一个程序，计算出将堆石子合并成一堆的最小得分。 【输入格式】 w第一行为一个正整数N (2100)； w以下行,每行一个正整数，小于10000，分别表示第i堆石子的个数 (1iN)。 【输出格式】 w为一个正整数，即最小得分。w si表示前i堆石头的价值总和，fij表示把第i堆到 第j堆的石头合并成一堆的最优值。 w for (i=n-1;i=1;i-) w for (j=i+1;j w#include wint min(int a,int b) w w return a b ? b:a; / 三目运算符，相当于if(ab) return b; else return a; w wint f101101; wint s101; wint n,i,j,k,x; wint main() w w scanf(“%d“, w for (i=1; i=1; i-) w for (j=i+1; j wlong long a1111,f1111; wlong long s; wint n,i,k,k1,j; wint max(int a, int b) w w return ab?a:b; w wint main() w w scanf(“%d%d“, w scanf(“%lld“, w for (i=n; i=1; i-) w w aii=s%10; w s/=10; w w for (i=2; i=1;j-) w aji=aji-1*10+aii; w w for (i=1; i w#include wint min(int a,int b)return a (h,k)）时 wsumijhk:=maxsumi-1jh-1k,sumij-1hk-1,sumi-1jhk-1,sumij- 1h-1k+aij+ahk; w当(i,j) = (h,k)时 wsumijhk:=maxsumi-1jh-1k,sumij-1hk-1,sumi-1jhk-1,sumij- 1h-1k+aij; w【参考程序1】 w#include wint max(int a,int b)return ab?a:b; wint a5151; wint sum51515151; wint n,i,j,h,k,x,y,z; wint main() w w scanf(“%d%d%d%d“, w while(x w scanf(“%d%d%d“, w w for (i=1; i w#include w#include wusing namespace std; wint max1(int,int); wint print(int,int); wint x,y,i,j,m,n,k,t,l; wint a501,f501501,d501; wint main() w w cinmk; w for (i=0;iaj; /输入m本书的页数 w dj=dj-1+aj; /dj为前j本书总的页数 w f1j=dj; /fij为一个人抄前j本书所需时间 w w for (i=2;iy) return x; else return y; w wint print(int i,int j) /递归输出抄写页数的方案 w w int t,x; w if (j=0) return 0; w if (j=1) /第1个人抄写1到i本书 w w cout w#include w#include wusing namespace std; wint main() w w int a101101,b101101,c101101,d101; /aij 花束i放在花瓶j中的美学值 w /bij 前i束花放在前j个花瓶中的最优解 w /cij 在bij的最优解中，花束i-1的位置 w int f,v,i,j,k,max; /f , v 花束和花瓶的数目 w cinfv; w for (i=1;iaij; w memset(b,128,sizeof(b); /这样处理，可以保证每束花都放进花瓶 w for (i=1;ibij) w w bij=bi-1k+aij; /更新当前最优解 w cij=k; /前一个花束的位置为k w max=-2100000000;for (i=f;imax)max=bfi; /选择全局最优解k=i; /k最后一束花的位置 cout=2;i-)cout #include #include using namespace std; void print(int,int); int max(int a,int b) return ab?a:b; int a101101,b101101; int main() int f,v;cinfv;for (int i=1;iaij;memset(b,128,sizeof(b); /初始化b数组for (int i=0;ic)c=bfi;cout0)n=i;while (bin!=j)n+; print(i-1,j-ain);cout #include using namespace std; int dx5=0,-1,0,1,0, /x的坐标增量dy5=0,0,1,0,-1; /y的坐标增量 long r,c,i,j,p,t,ans; long m101101,f101101; int search(int,int); int main() cinrc;ans=0;for (i=1;imij; /读入每个点的高度for (i=1;ians) ans=t; /寻找最大长度值 cout0) /此点长度已经求出，不必进行进一步递归，保证每 /一个点的最大长度只求一次，这是记忆化搜索的特点return (fxy); t=1;for (i=1;i=1) fxy=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 2 25 1 36 3 23 2、拔河比赛(tug.pas) 【问题描述】一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够 ）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体 重加起来尽可能地接近。 【输入格式】输入数据的第1行是一个n，表示参加拔河比赛的总人数，n=100，接下 来的n行表示第1到第n个人的体重，每个人的体重都是整数（1=weight=450 ） 【输出格式】输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空 格隔开。注意如果这两个数不相等，则请把小的放在前面输出。 【输入样例】tug.in 3 100 90 200 【输出样例】tug.out 1