资源描述
193第十章 动态规划 10.1 什么是动态规划 前面学过了用递归的方法解决问题。但是，单纯的递归，在解决某些问题的时候，效率会很低。例如下面这道题目：例题：数字三角形(ai2760)问题描述7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。输入数据输入的第一行是一个整数N(1 N=100)，给出三角形的行数。下面的N 行给出数字三角形。数字三角形上的数的范围都在0 和 100 之间。输出要求输出最大的和。输入样例5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出样例30 10.3 例题 最长上升子序列 275710.4 例题 Help Jimmy 166110.5 例题 最长公共子序列 280610.6 例题 陪审团的人选 29791 练习题 矩形覆盖 28092 练习题 金银岛 27953 练习题 滑雪 10884 练习题 采药 27335 练习题 Pell 数列 27866 练习题 集合加法 27927 练习题 木材加工 27748 练习题 最大子矩阵 2766 194解题思路 这道题目可以用递归的方法解决。基本思路是：以 D(r,j)表示第 r 行第 j 个数字(r，j 都从 1 开始算)，以 MaxSum(r,j)代表从第 r 行的第 j 个数字到底边的最佳路径的数字之和，则本题是要求 MaxSum(1,1)。从某个 D(r,j)出发，显然下一步只能走 D(r+1,j)或者 D(r+1,j+1)。如果走 D(r+1,j)，那么得到的 MaxSum(r,j)就是 MaxSum(r+1,j)+D(r,j)；如果走 D(r+1,j+1)，那么得到的MaxSum(r,j)就是 MaxSum(r+1,j+1)+D(r,j)。所以，选择往哪里走，就看 MaxSum(r+1,j)和MaxSum(r+1,j+1)哪个更大了。程序如下：1.#include 2.#define MAX_NUM 100 3.int DMAX_NUM+10MAX_NUM+10;4.int N;5.int MaxSum(int r,int j)6.7.if(r=N )8.return Drj;9.int nSum1=MaxSum(r+1,j);10.int nSum2=MaxSum(r+1,j+1);11.if(nSum1 nSum2)12.return nSum1+Drj;13.return nSum2+Drj;14.15.16.main()17.18.int m;19.scanf(%d,&N);20.for(int i=1;i=N;i+)21.for(int j=1;j=i;j+)22.scanf(%d,&Dij);23.printf(%d,MaxSum(1,1);24.上面的程序，效率非常低，在 N 值并不大，比如 N=100 的时候，就慢得几乎永远算不出结果了。为什么会这样呢？是因为过多的重复计算。我们不妨将对 MaxSum 函数的一次调用称为一次计算。那么，每次计算 MaxSum(r,j)的时候，都要计算一次 MaxSum(r+1,j)，而每次计算 MaxSum(r,j+1)的时候，也要计算一次 MaxSum(r+1,j)。重复计算因此产生。在题目中给出的例子里，如果我们将 MaxSum(r,j)被计算的次数都写在位置（r,j），那么就能得到下面的三角形：1 1 1 1 2 1 1 3 3 1 1951 4 6 4 1 从上图可以看出，最后一行的计算次数总和是 16，倒数第二行的计算次数总和是 8。不难总结出规律，对于 N 行的三角形，总的计算次数是 20+21+222N-1=2N。当 N=100 时，总的计算次数是一个让人无法接受的大数字。既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出 MaxSum(r,j)的值时，就将该值存放起来，下次再需要计算 MaxSum(r,j)时，直接取用存好的值即可，不必再次调用 MaxSum 进行函数递归计算了。这样，每个 MaxSum(r,j)都只需要计算 1 次即可，那么总的计算次数（即调用 MaxSum 函数的次数）就是三角形中的数字总数，即 1+2+3+N=N(N+1)/2 如何存放计算出来的 MaxSum（r,j）值呢？显然，用一个二维数组 aMaxSumNN 就能解决。aMaxSumrj 就存放 MaxSum(r,j)的计算结果。下次再需要 MaxSum(r,j)的值时，不必再调用 MaxSum 函数，只需直接取 aMaxSumrj的值即可。程序如下：1.#include 2.#include 3.#define MAX_NUM 100 4.int DMAX_NUM+10MAX_NUM+10;5.int N;6.int aMaxSumMAX_NUM+10MAX_NUM+10;7.int MaxSum(int r,int j)8.9.if(r=N )10.return Drj;11.if(aMaxSumr+1j=-1)/如果 MaxSum(r+1,j)没有计算过 12.aMaxSumr+1j=MaxSum(r+1,j);13.if(aMaxSumr+1j+1=-1)/如果 MaxSum(r+1,j+1)没有计算过 14.aMaxSumr+1j+1=MaxSum(r+1,j+1);15.if(aMaxSumr+1j aMaxSumr+1j+1)16.return aMaxSumr+1j+Drj;17.return aMaxSumr+1j+1+Drj;18.19.20.main()21.22.int m;23.scanf(%d,&N);24./将 aMaxSum 全部置成-1,表示开始所有的 MaxSum(r,j)都没有算过 25.memset(aMaxSum,-1,sizeof(aMaxSum);26.for(int i=1;i=N;i+)27.for(int j=1;j=i;j+)28.scanf(%d,&Dij);29.printf(%d,MaxSum(1,1);30.196这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：因此，不需要写递归函数，从 aMaxSumN-1这一行元素开始向上逐行递推，就能求得最终 aMaxSum11的值了。程序如下：1.#include 2.#include 3.#define MAX_NUM 100 4.int DMAX_NUM+10MAX_NUM+10;5.int N;6.int aMaxSumMAX_NUM+10MAX_NUM+10;7.main()8.9.int i,j;10.scanf(%d,&N);11.for(i=1;i=N;i+)12.for(j=1;j=i;j+)13.scanf(%d,&Dij);14.for(j=1;j 1;i-)17.for(j=1;j aMaxSumij+1)19.aMaxSumi-1j=aMaxSumij+Di-1j;20.else 21.aMaxSumi-1j=aMaxSumij+1+Di-1j;22.23.printf(%d,aMaxSum11);24.思考题 10.1：上面的几个程序只算出了最佳路径的数字之和。如果要求输出最佳路径上的每个数字，该怎么办？19710.2 动态规划解题的一般思路 许多求最优解的问题可以用动态规划来解决。用动态规划解题，首先要把原问题分解为若干个子问题，这一点和前面的递归方法类似。区别在于，单纯的递归往往会导致子问题被重复计算，而用动态规划的方法，子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的 n 变成了 n-1，或从原来的 nm 变成了 n(m-1)等等。找到子问题，就意味着找到了将整个问题逐渐分解的办法，因为子问题可以用相同的思路分解成子子问题，一直分解下去，直到最底层规模最小的的子问题可以一目了然地看出解（象上面数字三角形的递推公式中，r=N 时，解就是一目了然的）。每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。具体到数字三角形的例子，子问题就是“从位于(r，j)数字开始，到底边路径的最大和”。这个子问题和两个变量 r 和 j 相关，那么一个“状态”，就是 r,j 的一组取值，即每个数字的位置就是一个“状态”。该“状态”所对应的“值”，就是从该位置的数字开始，到底边的最佳路径上的数字之和。定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移即如何从一个或多个“值”已知的“状态”，求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。如下的递推式就说明了状态转移的方式：上面的递推式表明了如果知道了状态（r1，j）和状态（r+1，j+1）对应的值，该如何求出状态(r，j)对应的值，即两个子问题的解决，如何导致一个更高层的子问题的解决。所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里，一共有 N(N+1)/2 个数字，所以这个问题的状态空间里一共就有 N(N+1)/2 个状态。在该问题里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和 N 无关的常数。用动态规划解题，经常碰到的情况是，K 个整型变量能构成一个状态（如数字三角形中的行号和列号这两个变量构成“状态”）。如果这K个整型变量的取值范围分别是N1,N2,Nk，那么，我们就可以用一个 K 维的数组 arrayN1 N2Nk来存储各个状态的“值”。198这个“值”未必就是一个整数或浮点数，可能是需要一个结构才能表示的，那么 array 就可以是一个结构数组。一个“状态”下的“值”通常会是一个或多个子问题的解。用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转移方程”是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。甚至，对于同一个问题，分解成子问题的办法可能不止一种，因而“状态”也可以有不同的定义方法。不同的“状态”定义方法可能会导致时间、空间效率上的区别。10.3 例题：最长上升子序列 问题描述 一个数的序列 bi，当 b1 b2 .bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,.,aN)，我们可以得到一些上升的子序列(ai1,ai2,.,aiK)，这里 1=i1 i2 .iK=N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是 4，比如子序列(1,3,5,8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。输入数据 输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的 N 个整数，这些整数的取值范围都在 0 到 10000。输出要求 最长上升子序列的长度。输入样例 7 1 7 3 5 9 4 8 输出样例 4 解题思路 如何把这个问题分解成子问题呢？经过分析，发现“求以 ak（k=1,2,3N）为终点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这 N 个子问题都解决了，那么这 N 个子问题的解中，最大的那个就是整个问题的解。由上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置 k 就是“状态”，而状态 k 对应的“值”，就是以 ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有 N 个。状态定义出来后，转移方程就不难想了。假定 MaxLen(k)表示以ak做为“终点”的最长上升子序列的长度，那么：MaxLen(1)=1 MaxLen(k)=Max MaxLen(i)：1i k 且 ai ak且 k1 +1 这个状态转移方程的意思就是，MaxLen(k)的值，就是在 ak左边，“终点”数值小于 ak，且长度最大的那个上升子序列的长度再加 1。因为 ak左边任何“终点”小于 ak的子序列，加上 ak后就能形成一个更长的上升子序列。实际实现的时候，可以不必编写递归函数，因为从 MaxLen(1)就能推算出 MaxLen(2)，有了 MaxLen(1)和 MaxLen(2)就能推算出 MaxLen(3)参考程序：1991.#include 2.#include 3.#define MAX_N 1000 4.int bMAX_N+10;5.int aMaxLenMAX_N+10;6.main()7.8.int N;9.scanf(%d,&N);10.for(int i=1;i=N;i+)11.scanf(%d,&bi);12.aMaxLen1=1;13.for(i=2;i=N;i+)/每次求以第 i 个数为终点的最长上升子序列的长度 14.int nTmp=0;/记录满足条件的，第 i 个数左边的上升子序列的最大长度 15.for(int j=1;j bj)17.if(nTmp aMaxLenj)18.nTmp=aMaxLenj;19.20.21.aMaxLeni =nTmp+1;22.23.int nMax=-1;24.for(i=1;i=N;i+)25.if(nMax aMaxLeni)26.nMax=aMaxLeni;27.printf(%dn,nMax);28.常见问题 试图枚举全部上升子序列，然后在其中寻找最长的一个，导致超时错。思考题 10.3：改进此程序，使之能够输出最长上升子序列 10.4 例题：Help Jimmy 问题描述 Help Jimmy 是在下图所示的场景上完成的游戏：200 图 10-4 场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy 老鼠在时刻 0 从高于所有平台的某处开始下落，它的下落速度始终为 1 米/秒。当 Jimmy 落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是 1 米/秒。当 Jimmy 跑到平台的边缘时，开始继续下落。Jimmy 每次下落的高度不能超过 MAX 米，不然就会摔死，游戏也会结束。设计一个程序，计算 Jimmy 到地面时可能的最早时间。输入数据 第一行是测试数据的组数t（0=t=20）。每组测试数据的第一行是四个整数 N，X，Y，MAX，用空格分隔。N 是平台的数目（不包括地面），X 和 Y 是 Jimmy 开始下落的位置的横竖坐标，MAX 是一次下落的最大高度。接下来的 N 行每行描述一个平台，包括三个整数，X1i，X2i和 Hi。Hi表示平台的高度，X1i和 X2i表示平台左右端点的横坐标。1=N=1000，-20000=X,X1i,X2i=20000，0 Hi Y=20000（i=1.N）。所有坐标的单位都是米。Jimmy 的大小和平台的厚度均忽略不计。如果 Jimmy 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保 Jimmy 一定能安全到达地面。输出要求 对输入的每组测试数据，输出一个整数，Jimmy 到地面时可能的最早时间。输入样例 1 3 8 17 20 0 10 8 0 10 13 4 14 3 输出样例 23 解题思路 此题目的“子问题”是什么呢？Jimmy 跳到一块板上后，可以有两种选择，向左走，或向右走。走到左端和走到右端所需的时间，是很容易算的。如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。因此，整个问题就被分解成两个子问题，即 Jimmy 所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。将板子从上到下从 1 开始进行无重复的编号(越高的板子编号越小，高度相同的几块板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号，所以，本题目的“状态”就是板子编号，而一个“状态”对应的“值”有两部分，201是两个子问题的解，即从该板子左端出发到达地面的最短时间，和从该板子右端出发到达地面的最短时间。不妨认为 Jimmy 开始的位置是一个编号为 0，长度为 0 的板子，假设LeftMinTime(k)表示从 k 号板子左端到地面的最短时间，RightMinTime(k)表示从 k 号板子右端到地面的最短时间，那么，求板子 k 左端点到地面的最短时间的方法如下：if(板子 k 左端正下方没有别的板子)if(板子 k 的高度 h(k)大于 Max)LeftMinTime(k)=;else LeftMinTime(k)=h(k);else if(板子 k 左端正下方的板子编号是 m)LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k);上面，h(i)就代表 i 号板子的高度，Lx(i)就代表 i 号板子左端点的横坐标，Rx(i)就代表 i号板子右端点的横坐标。那么 h(k)-h(m)当然就是从 k 号板子跳到 m号板子所需要的时间，Lx(k)-Lx(m)就是从 m 号板子的落脚点走到 m 号板子左端点的时间，Rx(m)-Lx(k)就是从 m号板子的落脚点走到右端点所需的时间。求 RightMinTime(k)的过程类似。不妨认为 Jimmy 开始的位置是一个编号为 0，长度为 0 的板子，那么整个问题就是要求LeftMinTime(0)。输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。参考程序：(这个程序没有写注释是因为有时需要锻炼一下同学们读懂别人程序的能力)1.#include 2.#include 3.#include 4.#define MAX_N 1000 5.#define INFINITE 1000000 6.int t,n,x,y,max;7.struct Platform 8.int Lx,Rx,h;9.;10.Platform aPlatformMAX_N+10;11.int aLeftMinTimeMAX_N+10;12.int aRightMinTimeMAX_N+10;13.int MyCompare(const void*e1,const void*e2)14.15.Platform*p1,*p2;16.p1=(Platform*)e1;17.p2=(Platform*)e2;20218.return p2-h-p1-h;19.20.int MinTime(int L,bool bLeft)21.22.int y=aPlatformL.h;23.int x;24.if(bLeft)25.x=aPlatformL.Lx;26.else 27.x=aPlatformL.Rx;28.for(int i=L+1;i=n;i+)29.if(aPlatformi.Lx=x)30.break;31.32.if(i max)34.return INFINITE;35.36.else 37.if(y max)38.return INFINITE;39.else 40.return y;41.42.int nLeftTime=y-aPlatformi.h+x-aPlatformi.Lx;43.int nRightTime=y-aPlatformi.h +aPlatformi.Rx-x;44.if(aLeftMinTimei=-1)45.aLeftMinTimei=MinTime(i,true);46.if(aRightMinTimei=-1)47.aRightMinTimei=MinTime(i,false);48.nLeftTime+=aLeftMinTimei;49.nRightTime+=aRightMinTimei;50.if(nLeftTime nRightTime)51.return nLeftTime;52.return nRightTime;53.54.main()55.56.scanf(%d,&t);57.for(int i=0;i t;i+)58.memset(aLeftMinTime,-1,sizeof(aLeftMinTime);59.memset(aRightMinTime,-1,sizeof(aRightMinTime);60.scanf(%d%d%d%d,&n,&x,&y,&max);61.aPlatform0.Lx=x;20362.aPlatform0.Rx=x;63.aPlatform0.h=y;64.for(int j=1;j=n;j+)65.scanf(%d%d%d,&aPlatformj.Lx,&aPlatformj.Rx,&aPlatformj.h);66.qsort(aPlatform,n+1,sizeof(Platform),MyCompare);67.printf(%dn,MinTime(0,true);68.69.思考题 10.4：重新编写此程序，要求不使用递归函数 10.5 例题：最长公共子序列 问题描述 我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列，使得对 j=1,2,.,k,有 xij=zj。比如 Z=是 X=的子序列。现在给出两个序列 X 和 Y，你的任务是找到 X 和 Y 的最大公共子序列，也就是说要找到一个最长的序列 Z，使得 Z 既是 X 的子序列也是 Y 的子序列。输入数据 输入包括多组测试数据。每组数据包括一行，给出两个长度不超过 200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。输入样例 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0 解题思路 如果我们用字符数组 s1、s2 存放两个字符串，用 s1i表示 s1 中的第 i 个字符，s2j表示 s2 中的第 j 个字符（字符编号从 1 开始，不存在“第 0 个字符”），用 s1i表示 s1 的前 i个字符所构成的子串，s2j表示 s2 的前 j 个字符构成的子串，MaxLen(i,j)表示 s1i 和 s2j的最长公共子序列的长度，那么递推关系如下：if(i=0|j=0)MaxLen(i,j)=0/两个空串的最长公共子序列长度当然是 0 else if(s1i=s2j)MaxLen(i,j)=MaxLen(i-1,j-1)+1;else MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j);204 MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j)这个递推关系需要证明一下。我们用反证法来证明，MaxLen(i,j)不可能比 MaxLen(i,j-1)和 MaxLen(i-1,j)都大。先假设 MaxLen(i,j)比 MaxLen(i-1,j)大。如果是这样的话，那么一定是 s1i起作用了，即 s1i是 s1i 和 s2j的最长公共子序列里的最后一个字符。同样，如果 MaxLen(i,j)比 MaxLen(i,j-1)大，也能够推导出，s2j是 s1i 和 s2j的最长公共子序列里的最后一个字符。即，如果 MaxLen(i,j)比MaxLen(i,j-1)和 MaxLen(i-1,j)都大，那么，s1i应该和 s2j相等。但这是和应用本递推关系的前提-s1is2j相矛盾的。因此，MaxLen(i,j)不可能比 MaxLen(i,j-1)和 MaxLen(i-1,j)都大。MaxLen(i,j)当然不会比 MaxLen(i,j-1)和 MaxLen(i-1,j)中的任何一个小，因此，MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j)必然成立。显然本题目的“状态”就是 s1 中的位置 i 和 s2 中的位置 j。“值”就是 MaxLen(i,j)。状态的数目是 s1 长度和 s2 长度的乘积。可以用一个二维数组来存储各个状态下的“值”。本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。参考程序：1.#include 2.#include 3.#define MAX_LEN 1000 4.char sz1MAX_LEN;5.char sz2MAX_LEN;6.int aMaxLenMAX_LENMAX_LEN;7.main()8.9.while(scanf(%s%s,sz1+1,sz2+1)0)10.int nLength1=strlen(sz1+1);11.int nLength2=strlen(sz2+1);12.int nTmp;13.int i,j;14.for(i=0;i=nLength1;i+)15.aMaxLeni0=0;16.for(j=0;j=nLength2;j+)17.aMaxLen0j=0;18.for(i=1;i=nLength1;i+)19.for(j=1;j nLen2)27.aMaxLenij=nLen1;28.else 20529.aMaxLenij=nLen2;30.31.32.33.printf(%dn,aMaxLennLength1nLength2);34.35.常见问题 求解最长公共子序列时，当比较到两个字符串的两个字母不同时，应该分别将两个字符串向后移动一个字符，比较这两种情况中哪个得到的公共子序列最长。有些同学只将其中的一个字符串向后移动，或者两个同时移动，都是不对的。10.6 例题：陪审团的人选 问题描述 在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选 n 个人作为陪审团的候选人，然后再从这 n 个人中选 m 人组成陪审团。选 m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从 0 到 20。为了公平起见，法官选出陪审团的原则是：选出的 m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。输入数据 输入包含多组数据。每组数据的第一行是两个整数 n 和 m，n 是候选人数目，m 是陪审团人数。注意，1=n=200,1=m=20 而且 m=n。接下来的 n 行，每行表示一个候选人的信息，它包含 2 个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从 1开始编号。两组有效数据之间以空行分隔。最后一组数据 n=m=0 输出要求 对每组数据，先输出一行，表示答案所属的组号,如 Jury#1,Jury#2,等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。输入样例 4 2 1 2 2 3 4 1 6 2 0 0 输出样例 Jury#1 Best jury has value 6 for prosecution and value 4 for defence:2 3 206 解题思路 这道题目有一定难度。碰到求最优解的问题，都可以考虑一下能否用动态规划解决。为叙述问题方便，现将任一选择方案中，辩方总分和控方总分之差简称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。第i 个候选人的辩方总分和控方总分之差记为 V(i)，辩方总分和控方总分之和记为 S(i)。现用 f(j,k)表示，取 j 个候选人，使其辩控差为 k 的所有方案中，辩控和最大的那个方案（该方案称为“方案 f(j,k)”）的辩控和。并且，我们还规定，如果没法选 j 个人，使其辩控差为 k，那么 f(j,k)的值就为-1，也称方案 f(j,k)不可行。本题是要求选出 m 个人，那么，如果对 k 的所有可能的取值，求出了所有的 f(m,k)(-20m k 20m)，那么陪审团方案自然就很容易找到了。问题的关键是建立递推关系。需要从哪些已知条件出发，才能求出 f(j,k)呢？显然，方案f(j,k)是由某个可行的方案f(j-1,x)(-20m x 20m)演化而来的。可行方案 f(j-1,x)能演化成方案 f(j,k)的必要条件是：存在某个候选人 i，i 在方案 f(j-1,x)中没有被选上，且x+V(i)=k。在所有满足该必要条件的f(j-1,x)中，选出 f(j-1,x)+S(i)的值最大的那个，那么方案 f(j-1,x)再加上候选人 i，就演变成了方案 f(j,k)。这中间需要将一个方案都选了哪些人都记录下来。不妨将方案 f(j,k)中最后选的那个候选人的编号，记在二维数组的元素pathjk 中。那么方案 f(j,k)的倒数第二个人选的编号，就是 pathj-1k-Vpathjk。假定最后算出了解方案的辩控差是 k，那么从 pathmk出发，就能顺藤摸瓜一步步求出所有被选中的候选人。初始条件，只能确定 f(0,0)=0。由此出发，一步步自底向上递推，就能求出所有的可行方案 f(m,k)(-20m k 20m)。实际解题的时候，会用一个二维数组 f 来存放 f(j,k)的值。而且，由于题目中辩控差的值 k 可以为负数，而程序中数租下标不能为负数，所以，在程序中不妨将辩控差的值都加上400，以免下标为负数导致出错，即题目描述中，如果辩控差为 0，则在程序中辩控差为 400。参考程序(来自学生提交的程序)1.#include 2.#include 3.#include 4.int f301000;5./fj,k表示，取 j 个候选人，使其辩控差为 k 的所有方案中，6./辩控和最大的那个方案（该方案称为方案 f(j,k)）的辩控和。7.int Path301000;8./Path 数组用来记录选了哪些人 9./方案 f(j,k)中最后选的那个候选人的编号，记在 Pathjk中 10.int P300;/控方打分 11.int D300;/辩方打分 12.int Answer30;/存放最终方案的人选 13.14.int CompareInt(const void*e1,const void*e2)15.16.return*(int*)e1)-*(int*)e2);17.20718.int main()19.20.int i,j,k;21.int t1,t2;22.int n,m;23.int nMinP_D;/辩控双方总分一样时的辩控差 24.int nCaseNo;/测试数据编号 25.nCaseNo=0;26.scanf(%d%d,&n,&m);27.while(n+m)28.nCaseNo+;29.for(i=1;i=n;i+)30.scanf(%d%d,&Pi,&Di);31.memset(f,-1,sizeof(f);32.memset(Path,0,sizeof(Path);33.nMinP_D=m*20;/题目中的辩控差为 0，对应到程序中辩控差就是 m*20 34.f0nMinP_D=0;/选 0 个人使得辩控差为 nMinP_D 的方案，其辩控和就是 0 35.for(j=0;jm;j+)/每次循环选出第 j 个人，共要选出 m 人 36.for(k=0;k=0)/方案 f(j,k)可行 38.for(i=1;ifj+1k+Pi-Di)40.t1=j;t2=k;41.while(t10&Patht1t2!=i)42.t2-=PPatht1t2-DPatht1t2;43.t1-;44.45.if(t1=0)46.fj+1k+Pi-Di=fjk+Pi+Di;47.Pathj+1k+Pi-Di=i;48.49.50.51.52.i=nMinP_D;53.j=0;54.while(fmi+j0&fmi-jfmi-j)57.k=i+j;58.else 59.k=i-j;60.printf(Jury#%dn,nCaseNo);61.printf(Best jury has value%d for prosecution and value%d for defence:n,20862.(k-nMinP_D+fmk)/2,(fmk-k+nMinP_D)/2);63.for(i=1;i=m;i+)64.Answeri=Pathm-i+1k;65.k-=PAnsweri-DAnsweri;66.67.qsort(Answer+1,m,sizeof(int),CompareInt);68.for(i=1;i 2)。给出一个正整数 k(1 k 1000000)，要求 Pell 数列的第 k 项除以 32767 的余数是多少。2106.集合加法给出 2 个正整数集合 A=pi|1=i=a，B=qj|1=j=b和一个正整数 s(1=s=10000)。问题是：使得 pi+qj=s 的不同的(i,j)对有多少个。7.木材加工木材厂有 N 根原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目 K 是给定了。我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是 cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数(1=N=10000，1=K=10000)。8.最大子矩阵将“矩阵的大小”定义为矩阵中所有元素的和。给定一个 N*N 的矩阵(0 N=100)，你的任务是找到最大的非空(大小至少是 1*1)子矩阵。比如，如下 4*4 的矩阵 0-2-7 0 9 2-6 2 -4 1-4 1-1 8 0-2 它的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是 15。
展开阅读全文