当前位置:首页 >> IT/计算机 >>

动态规划基础讲解及经典案例分析解答


综合实践考核
第九课

动态规划(I) 动态规划( )
2011-3-6 1

数字三角形
1、问题描述 、

上图给出了一个数字三角形。 上图给出了一个数字三角形。从三角形的顶部到底部有很多条 不同的路径。对于每条路径, 不同的路径。对于每条路径,把路径上面的数加起来可以得到 一个和,和最大的路径称为最佳路径。 一个和,和最大的路径称为最佳路径。你的任务就是求出最佳 路径上的数字之和。 路径上的数字之和。 注意: 注意:路径上的每一步只能从一个数走到下一层上和它最近的 左边的数或者右边的数。 左边的数或者右边的数。

问题描述
输入数据
输入的第一行是一个整数N 输入的第一行是一个整数 (1 < N <= 100),给出 , 三角形的行数。下面的N 行给出数字三角形。数字三 三角形的行数。下面的 行给出数字三角形。 角形上的数的范围都在0 之间。 角形上的数的范围都在0 和100 之间。

输出要求
输出最大的和。 输出最大的和。

问题描述
输入样例
5 7 38 810 2744 45265

输出样例
30

2、解题思路
这道题目可以用递归的方法解决。基本思路是: 这道题目可以用递归的方法解决。基本思路是: 表示第r 个数字(r, 都从1 开始算), 以D( r, j)表示第 行第 j 个数字 ,j 都从 开始算 ,以 表示第 MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的最佳路径 的数字之和, 的数字之和,则本题是要求 MaxSum(1, 1) 。 从某个D(r, j)出发,显然下一步只能走 出发, 或者D(r+1, 从某个 出发 显然下一步只能走D(r+1, j)或者 或者 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)哪个更大了。 哪个更大了。 哪个更大了

3、参考程序 I
#include <stdio.h> #define MAX_NUM 100 int D[MAX_NUM + 10][MAX_NUM + 10]; int N; int MaxSum( int r, int j) { if( r == N ) return D[r][j]; int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 > nSum2 ) return nSum1+D[r][j]; return nSum2+D[r][j]; }

3、参考程序 I
int main(void) { int m; scanf("%d", &N); for( int i = 1; i <= N; i ++ ) for( int j = 1; j <= i; j ++ ) scanf("%d", &D[i][j]); printf("%d", MaxSum(1, 1)); return 0; }

提交结果: 提交结果:Time Limit Exceed

程序I分析
上面的程序,效率非常低, 值并不大, 上面的程序 , 效率非常低 , 在 N 值并不大 , 比如N=100 的时候,就慢得几乎永远算不出 的时候, 比如 结果了。 结果了。 为什么会这样呢?是因为过多的重复计算。 为什么会这样呢?是因为过多的重复计算。 我们不妨将对MaxSum 函数的一次调用称为 我们不妨将对 一次计算。那么,每次计算MaxSum(r, j)的 一次计算。那么,每次计算 的 时候,都要计算一次MaxSum(r+1, j+1), 时候,都要计算一次 , 而每次计算MaxSum(r, j+1)的时候 , 也要 的时候, 而每次计算 的时候 计算一次MaxSum(r+1, j+1)。重复计算因 计算一次 。 此产生。 此产生。 在题目中给出的例子里,如果我们将 MaxSum(r, j)被计算的次数都写在位置(r, 被计算的次数都写在位置( 被计算的次数都写在位置 j),那么就能得到右面的三角形: ) 那么就能得到右面的三角形: 7 38 810 2744 45265 1 11 121 1331 14641

从上图可以看出,最后一行的计算次数总和是 , 从上图可以看出,最后一行的计算次数总和是16,倒数第二行 的计算次数总和是8。不难总结出规律,对于N 行的三角形,总 的计算次数总和是 。不难总结出规律,对于 行的三角形, 的计算次数是2^0 +2^1+2^2+…+2^(N-1)=2^N-1。当 的计算次数是 。 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)值呢?显然,用一个二维 ( )值呢?显然, 如何存放计算出来的 数组aMaxSum[N][N]就能解决。aMaxSum[r][j]就存放 就能解决。 数组 就能解决 就存放 MaxSum(r, j)的计算结果。下次再需要 的计算结果。 的值时, 的计算结果 下次再需要MaxSum(r, j)的值时, 的值时 不必再调用MaxSum 函数,只需直接取aMaxSum[r][j]的值即 不必再调用 函数,只需直接取 的值即 可。

程序分析

4、参考程序 II
#include <stdio.h> #include <memory.h> #define MAX_NUM 100 int D[MAX_NUM + 10][MAX_NUM + 10]; int N; int aMaxSum[MAX_NUM + 10][MAX_NUM + 10]; int MaxSum( int r, int j) { if( r == N ) return D[r][j]; if( aMaxSum[r+1][j] == -1 ) //如果 如果MaxSum(r+1, j)没有计算过 没有计算过 如果 aMaxSum[r+1][j] = MaxSum(r+1, j); if( aMaxSum[r+1][j+1] == -1) aMaxSum[r+1][j+1] = MaxSum(r+1, j+1); if( aMaxSum[r+1][j] > aMaxSum[r+1][j+1] ) return aMaxSum[r+1][j] +D[r][j]; return aMaxSum[r+1][j+1] + D[r][j]; }

4、参考程序 II
int main(void) { int m; scanf("%d", & N); //将 aMaxSum 全部置成 将 全部置成-1, 开始时所有的 MaxSum(r, j)都没有算过 都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum)); for( int i = 1; i <= N; i ++ ) for( int j = 1; j <= i; j ++ ) scanf("%d", & D[i][j]); printf("%d", MaxSum(1, 1)); return 0; }

程序II分析
这种将一个问题分解为子问题递归求解, 这种将一个问题分解为子问题递归求解,并且将中间结果 保存以避免重复计算的办法,就叫做“动态规划” 保存以避免重复计算的办法,就叫做“动态规划”。动态规 划通常用来求最优解,能用动态规划解决的求最优解问题, 划通常用来求最优解,能用动态规划解决的求最优解问题, 必须满足,最优解的每个局部解也都是最优的。以上题为例, 必须满足,最优解的每个局部解也都是最优的。以上题为例, 最佳路径上面的每个数字到底部的那一段路径, 最佳路径上面的每个数字到底部的那一段路径,都是从该数 字出发到达到底部的最佳路径。 字出发到达到底部的最佳路径。 实际上,递归的思想在编程时未必要实现为递归函数。在上 实际上,递归的思想在编程时未必要实现为递归函数。 面的例子里,有递推公式: 面的例子里,有递推公式:
r=N ?D[r][j] ? ? aMaxSum[r][j] = ? ?Max(aMaxSum[r + 1][j], ? aMaxSum[r + 1][j + 1]) + D[r][j] 其他 ?

因此,不需要写递归函数, 因此,不需要写递归函数,从aMaxSum[N-1]这一行元素 这一行元素 开始向上逐行递推,就能求得aMaxSum[1][1]的值了。 的值了。 开始向上逐行递推,就能求得 的值了

int D[MAX_NUM + 10][MAX_NUM + 10]; int N; int aMaxSum[MAX_NUM + 10][MAX_NUM + 10]; int main(void) { int i, j; 思考题: 思考题:上面的几个程序 scanf("%d", & N); for( i = 1; i <= N; i ++ ) 只算出了最佳路径的数字 for( j = 1; j <= i; j ++ ) 之和。 之和。如果要求输出最佳 scanf("%d", &D[i][j]); 路径上的每个数字, 路径上的每个数字,该怎 for( j = 1; j <= N; j ++ ) aMaxSum[N][j] = D[N][j]; 么办? 么办? for( i = N ; i > 1 ; i -- ) for( j = 1; j < i ; j ++ ) { if( aMaxSum[i][j] > aMaxSum[i][j+1] ) aMaxSum[i-1][j] = aMaxSum[i][j] + D[i-1][j]; else aMaxSum[i-1][j] = aMaxSum[i][j+1] + D[i-1][j]; } printf("%d", aMaxSum[1][1]); return 0; }

5、参考程序 III

动态规划解题的一般思路
许多求最优解的问题可以用动态规划来解决。 许多求最优解的问题可以用动态规划来解决。 首先要把原问题分解为若干个子问题。 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导 致子问题被重复计算,用动态规划的方法, 致子问题被重复计算,用动态规划的方法,子问题的解一旦求出就 要被保存,所以每个子问题只需求解一次。 要被保存,所以每个子问题只需求解一次。 子问题经常和原问题形式相似,有时甚至完全一样, 子问题经常和原问题形式相似,有时甚至完全一样,只不过规模 从原来的n 变成了n-1,或从原来的 ×m 变成了 ×(m-1) ……等 从原来的 变成了 ,或从原来的n× 变成了n× 等 等。 找到子问题,就意味着找到了将整个问题逐渐分解的办法。 找到子问题,就意味着找到了将整个问题逐渐分解的办法。 分解下去, 分解下去,直到最底层规模最小的的子问题可以一目了然地看出 解。 每一层子问题的解决,会导致上一层子问题的解决,逐层向上, 每一层子问题的解决,会导致上一层子问题的解决,逐层向上, 就会导致最终整个问题的解决。 就会导致最终整个问题的解决。 如果从最底层的子问题开始, 如果从最底层的子问题开始,自底向上地推导出一个个子问题的 那么编程的时候就不需要写递归函数。 解,那么编程的时候就不需要写递归函数。

动态规划解题的一般思路
用动态规划解题时,将和子问题相关的各个变量的一组取值, 用动态规划解题时,将和子问题相关的各个变量的一组取值, 称之为一个“状态” 一个“状态”对应于一个或多个子问题, 称之为一个“状态”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“ 就是这个“状态” 所谓某个“状态”下的“值”,就是这个“状态”所对应的子 问题的解。 问题的解。 比如数字三角形,子问题就是“从位于(r, 数字开始 数字开始, 比如数字三角形,子问题就是“从位于 ,j)数字开始,到 底边路径的最大和” 这个子问题和两个变量r 相关, 底边路径的最大和”。这个子问题和两个变量 和j 相关,那 么一个“状态” 就是r, 的一组取值, 么一个“状态”,就是 j 的一组取值,即每个数字的位置就 是一个“状态” 状态”所对应的“ 是一个“状态”。该“状态”所对应的“值”,就是从该位置 的数字开始,到底边的最佳路径上的数字之和。 的数字开始,到底边的最佳路径上的数字之和。 定义出什么是“状态” 状态”下的“ 定义出什么是“状态”,以及在该 “状态”下的“值”后, 就要找出不同的状态之间如何迁移――即如何从一个或多个 就要找出不同的状态之间如何迁移 即如何从一个或多个 状态” 求出另一个“状态” “值”已知的 “状态”,求出另一个“状态”的“值”。状 态的迁移可以用递推公式表示,此递推公式也可被称作“ 态的迁移可以用递推公式表示,此递推公式也可被称作“状态 转移方程” 转移方程”。

动态规划解题的一般思路
r=N ? D[r][j] ? ? aMaxSum[r][j] = ? ? Max(aMaxSum[r + 1][j], ? aMaxSum[r + 1][j + 1]) + D[r][j] 其他 ?

用动态规划解题, 如何寻找 “ 子问题 ” , 定义 “ 状态 ” , 用动态规划解题 , 如何寻找“ 子问题” 定义“ 状态” 状态转移方程”是什么样的,并没有一定之规, “状态转移方程”是什么样的,并没有一定之规,需要具体问 题具体分析,题目做多了就会有感觉。 题具体分析,题目做多了就会有感觉。 甚至,对于同一个问题,分解成子问题的办法可能不止一种, 甚至, 对于同一个问题,分解成子问题的办法可能不止一种 , 因而“状态”也可以有不同的定义方法。不同的“状态” 因而“状态”也可以有不同的定义方法。不同的“状态”定义 方法可能会导致时间、空间效率上的区别。 方法可能会导致时间、空间效率上的区别。

最长上升子序列
1、问题描述 、
一个数的序列b 的时候, 一个数的序列 i,当b1 < b2 < ... < bS 的时候, 我们称这个序列是上升的。对于给定的一个序列(a 我们称这个序列是上升的。 对于给定的一个序列 1, a2, ..., aN), 我们可以得到一些上升的子序列 i1, , 我们可以得到一些上升的子序列(a ai2, ..., aiK),这里 <= i1 < i2 < ... <iK <= N。 ,这里1 。 比如,对于序列(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 1735948 输出样例 4

2、解题思路
如何把这个问题分解成子问题呢?经过分析, 如何把这个问题分解成子问题呢?经过分析,发现 “求以 ak(k=1, 2, 3…N)为终点的最长上升子序列的长度”是个 ( )为终点的最长上升子序列的长度” 好的子问题――这里把一个上升子序列中最右边的那个数,称 这里把一个上升子序列中最右边的那个数, 好的子问题 这里把一个上升子序列中最右边的那个数 为该子序列的“终点” 为该子序列的“终点”。虽然这个子问题和原问题形式上并不 完全一样,但是只要这N 个子问题都解决了,那么这N 完全一样,但是只要这 个子问题都解决了,那么这 个子问 题的解中,最大的那个就是整个问题的解。 题的解中,最大的那个就是整个问题的解。 由上所述的子问题只和一个变量相关,就是数字的位置。 由上所述的子问题只和一个变量相关,就是数字的位置。因 此序列中数的位置k 就是“状态” 对应的“ 此序列中数的位置 就是“状态”,而状态 k 对应的“值”, 就是以ak 做为“终点”的最长上升子序列的长度。 就是以 做为“终点”的最长上升子序列的长度。这个问题 的状态一共有N 状态定义出来后,转移方程就不难想了。 的状态一共有 个。状态定义出来后,转移方程就不难想了。

2、解题思路
假定MaxLen (k)表示以 k 做为“终点”的最长上升子序列 表示以a 做为“终点” 假定 表示以 的长度,那么: 的长度,那么: MaxLen (1) = 1 MaxLen (k) = Max { MaxLen (i):1<i < k 且 ai < ak 且 : k≠1 } + 1 这个状态转移方程的意思就是, 的值, 这个状态转移方程的意思就是,MaxLen(k)的值,就是在 k 的值 就是在a 左边, 终点”数值小于a 左边,“终点”数值小于 k,且长度最大的那个上升子序列的 长度再加1。因为a 左边任何“终点”小于a 的子序列, 长度再加 。因为 k 左边任何“终点” 小于 k 的子序列,加 后就能形成一个更长的上升子序列。 上ak 后就能形成一个更长的上升子序列。 实际实现的时候,可以不必编写递归函数,因为从 MaxLen(1) 就 能 推 算 出 MaxLen(2) , 有 了 MaxLen(1) 和 MaxLen(2)就能推算出 就能推算出MaxLen(3)…… 就能推算出

3、参考程序
int b[MAX_N + 10]; int aMaxLen[MAX_N + 10]; int main(void) { int i, j, N; scanf("%d", & N); for( i = 1;i <= N;i ++ ) scanf("%d", & b[i]); aMaxLen[1] = 1;

for( i = 2; i <= N; i ++ ) { //求以第 个数为终点的最长上升子序列的长度 求以第i 求以第 int nTmp = 0; //记录第 个数左边子序列最大长度 记录第i 记录第 for( j = 1; j < i; j ++ ) { //搜索以第 个数左边数为终点的最长上升子序列长度 搜索以第i 搜索以第 if( b[i] > b[j] ) { if( nTmp < aMaxLen[j] ) nTmp = aMaxLen[j]; } } aMaxLen[i] = nTmp + 1; } int nMax = -1; for( i = 1;i <= N;i ++ ) if( nMax < aMaxLen[i]) nMax = aMaxLen[i]; 思考题:改进此程序, 思考题:改进此程序,使之 printf("%d\n", nMax); 能够输出最长上升子序列 return 0; }

3、参考程序

Help Jimmy
1、问题描述 、
"Help Jimmy" 是在下图所示的场景上完成的游戏: 是在下图所示的场景上完成的游戏:

问题描述
场景中包括多个长度和高度各不相同的平台。 场景中包括多个长度和高度各不相同的平台。地面是最低 的平台,高度为零,长度无限。 的平台,高度为零,长度无限。 Jimmy 老鼠在时刻 从高于所有平台的某处开始下落,它 老鼠在时刻0 从高于所有平台的某处开始下落, 的下落速度始终为1 落到某个平台上时, 的下落速度始终为 米/秒。当Jimmy 落到某个平台上时,游 秒 戏者选择让它向左还是向右跑,它跑动的速度也是1 戏者选择让它向左还是向右跑,它跑动的速度也是 米/秒。 秒 跑到平台的边缘时,开始继续下落。 当Jimmy 跑到平台的边缘时,开始继续下落。Jimmy 每次下 落的高度不能超过MAX 米,不然就会摔死,游戏也会结束。 不然就会摔死,游戏也会结束。 落的高度不能超过 设计一个程序,计算 到地面时可能的最早时间。 设计一个程序,计算Jimmy 到地面时可能的最早时间。

问题描述
输入数据
第一行是测试数据的组数t( )。每组测试数 第一行是测试数据的组数 (0 <= t <= 20)。每组测试数 )。 据的第一行是四个整数N, , , 据的第一行是四个整数 ,X,Y,MAX,用空格分隔。N 是 ,用空格分隔。 平台的数目(不包括地面), ),X 平台的数目(不包括地面), 和Y 是Jimmy 开始下落的位 置的横竖坐标, 是一次下落的最大高度。接下来的N 置的横竖坐标,MAX 是一次下落的最大高度。接下来的 行 每行描述一个平台,包括三个整数, 每行描述一个平台,包括三个整数,X1[i],X2[i]和H[i]。 , 和 。 H[i]表示平台的高度,X1[i]和X2[i]表示平台左右端点的横坐 表示平台的高度, 表示平台的高度 和 表示平台左右端点的横坐 标。1<= N <= 1000,-20000 <= X, X1[i], X2[i] <= , 20000,0 < H[i] < Y <= 20000(i = 1..N)。所有坐标 )。所有坐标 , ( )。 的单位都是米。 的单位都是米。 Jimmy 的大小和平台的厚度均忽略不计。如果 的大小和平台的厚度均忽略不计。如果Jimmy 恰好 落在某个平台的边缘,被视为落在平台上。 落在某个平台的边缘,被视为落在平台上。所有的平台均不重 叠或相连。测试数据保Jimmy 一定能安全到达地面。 一定能安全到达地面。 叠或相连。测试数据保

问题描述
输出要求
对输入的每组测试数据,输出一个整数, 对输入的每组测试数据,输出一个整数,Jimmy 到地面时可 能的最早时间。 能的最早时间。

输入样例
1 3 8 17 20 0 10 8 0 10 13 4 14 3

输出样例
23

2、解题思路
此题目的“子问题”是什么呢? 此题目的“子问题”是什么呢? Jimmy 跳到一块板上后,可以有两种选择,向左走或向右 跳到一块板上后,可以有两种选择, 走到左端和走到右端所需的时间,容易算出。 走。走到左端和走到右端所需的时间,容易算出。 如果我们能知道,以左端为起点到达地面的最短时间, 如果我们能知道,以左端为起点到达地面的最短时间,和以 右端为起点到达地面的最短时间,那么向左走还是向右走, 右端为起点到达地面的最短时间,那么向左走还是向右走,就 很容选择了。 很容选择了。 因此,整个问题就被分解成两个子问题, 因此,整个问题就被分解成两个子问题,即Jimmy 所在位 置下方第一块板左端为起点到地面的最短时间, 置下方第一块板左端为起点到地面的最短时间,和右端为起点 到地面的最短时间。 到地面的最短时间。这两个子问题在形式上和原问题是完全一 致的。 致的。 将板子从上到下从1 开始进行无重复的编号(高度相同的板 将板子从上到下从 开始进行无重复的编号 高度相同的板 哪块编号在前无所谓),那么, 子,哪块编号在前无所谓 ,那么,和上面两个子问题相关的 变量就只有板子的编号。 变量就只有板子的编号。

所以,本题目的“状态”就是板子编号,而一个“状态” 所以,本题目的“状态”就是板子编号,而一个“状态”对 应的“ 有两部分,是两个子问题的解, 应的“值”有两部分,是两个子问题的解,即从该板子左端出 发到达地面的最短时间, 发到达地面的最短时间,和从该板子右端出发到达地面的最短 时间。 时间。 不妨认为Jimmy 开始的位置是一个编号为 ,长度为 的板 开始的位置是一个编号为0,长度为0 不妨认为 假设LeftMinTime(k)表示从 号板子左端到地面的最短 表示从k 子,假设 表示从 时间, 表示从k 时间,RightMinTime(k)表示从 号板子右端到地面的最短 表示从 时间,那么,求板子k 左端点到地面的最短时间的方法如下: 时间,那么,求板子 左端点到地面的最短时间的方法如下:
if ( 板子 左端正下方没有别的板子 板子k 左端正下方没有别的板子) { if( 板子 的高度 h(k) 大于 板子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));

2、解题思路

2、解题思路
上面, 就代表i 就代表i 上面,h(i)就代表 号板子的高度,Lx(i)就代表 号板子左 就代表 号板子的高度, 就代表 端点的横坐标,Rx(i)就代表 号板子右端点的横坐标。那么 端点的横坐标, 就代表i号板子右端点的横坐标。 就代表 号板子右端点的横坐标 h(k)-h(m) 当然就是从 号板子跳到 号板子所需要的时间, 当然就是从k 号板子跳到m 号板子所需要的时间, Lx(k)-Lx(m) 就是从 号板子的落脚点走到 号板子左端点 就是从m 号板子的落脚点走到m 的时间, 就是从m号板子的落脚点走到右端点 的时间,Rx(m)-Lx(k)就是从 号板子的落脚点走到右端点 就是从 所需的时间。 所需的时间。 的过程类似。 求RightMinTime(k)的过程类似。 的过程类似 不妨认为Jimmy 开始的位置是一个编号为 ,长度为 的板 开始的位置是一个编号为0,长度为0 不妨认为 那么整个问题就是要求LeftMinTime(0)。 子,那么整个问题就是要求 。 输入数据中,板子并没有按高度排序, 输入数据中,板子并没有按高度排序,所以程序中一定要首 先将板子排序。 先将板子排序。

#include <stdio.h> #include <memory.h> #include <stdlib.h> #define MAX_N 1000 #define INFINITE 1000000 int t, n, x, y, max; struct Platform { int Lx, Rx, h; }; Platform aPlatform[MAX_N + 10]; int aLeftMinTime[MAX_N + 10]; int aRightMinTime[MAX_N + 10]; int MyCompare( const void * e1, const void * e2 ) { Platform * p1, * p2; p1 = (Platform * ) e1; p2 = (Platform * ) e2; return p2->h - p1->h; //从大到小排列 从大到小排列 }

3、参考程序

3、参考程序
int MinTime( int L, bool bLeft ) { int y = aPlatform[L].h; int i, x; if( bLeft ) x = aPlatform[L].Lx; else x = aPlatform[L].Rx; for( i = L + 1;i <= n;i ++ ) //找到下一张板子 //找到下一张板子 { if( aPlatform[i].Lx <= x && aPlatform[i].Rx >= x) break; } if( i <= n ) //找到了 找到了 { if( y - aPlatform[i].h > max )//太高 太高 return INFINITE; }

else //没找到 没找到 { if( y > max )//离地面太高 离地面太高 return INFINITE; else return y; }//特殊情况处理完毕 特殊情况处理完毕 int nLeftTime = y - aPlatform[i].h + x - aPlatform[i].Lx; int nRightTime = y - aPlatform[i].h + aPlatform[i].Rx - x; if( aLeftMinTime[i] == -1 )//还没有存储值 还没有存储值 aLeftMinTime[i] = MinTime(i, true); if( aRightMinTime[i] == -1 ) aRightMinTime[i] = MinTime(i, false); nLeftTime += aLeftMinTime[i]; nRightTime += aRightMinTime[i]; if( nLeftTime < nRightTime ) return nLeftTime; return nRightTime; }

3、参考程序

int main(void) { scanf("%d", &t); for( int i = 0;i < t; i ++ ) { memset(aLeftMinTime, -1, sizeof(aLeftMinTime)); memset(aRightMinTime, -1, sizeof(aRightMinTime)); scanf("%d%d%d%d", &n, &x, &y, &max); aPlatform[0].Lx = x; aPlatform[0].Rx = x;//长度为 的板子 长度为0的板子 长度为 aPlatform[0].h = y; for( int j = 1; j <= n; j ++ ) scanf("%d%d%d", & aPlatform[j].Lx, & aPlatform[j].Rx, & aPlatform[j].h); qsort(aPlatform, n+1, sizeof(Platform), MyCompare); printf("%d\n", MinTime(0, true)); } 思考题:重新编写此程序, 思考题:重新编写此程序,要求不使用递 return 0; 归函数 }

3、参考程序

综合实践考核
第十课

动态规划(II) 动态规划( )
2011-3-6 34

最长公共子序列
1、问题描述 、
我们称序列Z 是序列X 我们称序列 = < z1, z2, ..., zk >是序列 = < x1, x2, ..., 是序列 xm >的子序列当且仅当存在严格上升的序列 i1, i2, ..., ik >, 的子序列当且仅当存在严格上升的序列< 的子序列当且仅当存在严格上升的序列 , 使得对j 比如Z 使得对 = 1, 2, ... ,k, 有xij = zj。比如 = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 的子序列。 的子序列 现在给出两个序列X Y,你的任务是找到X 现在给出两个序列X 和Y,你的任务是找到X 和Y 的最大公共 子序列,也就是说要找到一个最长的序列Z,使得Z 既是X 子序列,也就是说要找到一个最长的序列 ,使得 既是 的 子序列也是Y 的子序列。 子序列也是 的子序列。

?输入数据 输入数据
输入包括多组测试数据。每组数据包括一行, 输入包括多组测试数据。每组数据包括一行,给出两个长度不 超过200 的字符串 , 表示两个序列 。 两个字符串之间由若干 的字符串,表示两个序列。 超过 个空格隔开。 个空格隔开。

问题描述
? 输出要求
对每组输入数据,输出一行, 对每组输入数据,输出一行,给出两个序列的最大公共子序 列的长度。 列的长度。

? 输入样例
abcfbc abfcab programming contest abcd mnp

? 输出样例
4 2 0

2、解题思路
用字符数组s1、 存放两个字符串 存放两个字符串, 表示s1中的第 用字符数组 、s2存放两个字符串,用s1[i]表示 中的第 表示 中的第i 个字符,s2[j]表示 中的第j个字符(字符编号从1 开始), 个字符, 表示s2中的第 个字符(字符编号从 开始) 表示 中的第 个字符 表示s1的前 个字符所构成的子串, 表示s2的前 的前i个字符所构成的子串 的前j个字 用s1i表示 的前 个字符所构成的子串,s2j表示 的前 个字 符构成的子串, 表示s1 符构成的子串,MaxLen(i,j)表示 i 和s2j 的最长公共子序列 表示 的长度,那么递推关系如下: 的长度,那么递推关系如下: if( i ==0 || j == 0 ) MaxLen(i, j) = 0 //两个空串的最长公共子序列长度是 两个空串的最长公共子序列长度是0 两个空串的最长公共子序列长度是 else if( s1[i] == s2[j] ) MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j));

2、解题思路
显然本题目的“状态”就是s1 中的位置 和 中的位置i 显然本题目的“状态”就是 s2 中的位置 。 中的位置j。 “值”就是MaxLen(i, j)。 就是 。 状态的数目是s1 长度和 长度和s2 长度的乘积。可 长度的乘积。 状态的数目是 以用一个二维数组来存储各个状态下的“ 以用一个二维数组来存储各个状态下的“值”。 本问题的两个子问题, 本问题的两个子问题,和原问题形式完全一 致的,只不过规模小了一点。 致的,只不过规模小了一点。

3、参考程序
#include <stdio.h> #include <string.h> #define MAX_LEN 1000 char sz1[MAX_LEN]; char sz2[MAX_LEN]; int aMaxLen[MAX_LEN][MAX_LEN]; int main(void) { while( scanf("%s%s", sz1+1 ,sz2+1 ) > 0 ) { int nLength1 = strlen( sz1+1); int nLength2 = strlen( sz2+1); int i, j; for( i = 0;i <= nLength1; i ++ ) aMaxLen[i][0] = 0; for( j = 0;j <= nLength2; j ++ ) aMaxLen[0][j] = 0;

for( i = 1;i <= nLength1;i ++ ) { for( j = 1; j <= nLength2; j ++ ) { if( sz1[i] == sz2[j] ) aMaxLen[i][j] = aMaxLen[i-1][j-1] + 1; else { int nLen1 = aMaxLen[i][j-1]; int nLen2 = aMaxLen[i-1][j]; if( nLen1 > nLen2 ) aMaxLen[i][j] = nLen1; else aMaxLen[i][j] = nLen2; } } } printf("%d\n", aMaxLen[nLength1][nLength2]);

3、参考程序

} return 0; }

陪审团的人选
1、问题描述 、
在遥远的国家佛罗布尼亚, 嫌犯是否有罪, 在遥远的国家佛罗布尼亚 , 嫌犯是否有罪 , 须由陪审团决 陪审团是由法官从公众中挑选的。先随机挑选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', 等。接下来的一行要象例子那样输出陪审团 的控方总分和辩方总分。 的控方总分和辩方总分。再下来一行要以升序输出陪审团里每 个成员的编号,两个成员编号之间用空格分隔。 个成员的编号,两个成员编号之间用空格分隔。每组输出数据 须以一个空行结束。 须以一个空行结束。

问题描述
输入样例
42 12 23 41 62 00

输出样例
Jury #1 Best jury has value 6 for prosecution and value 4 for defence: 23

2、解题思路
为叙述方便,将任一选择方案中,辩方总分和控方总分之差 为叙述方便, 将任一选择方案中, 简称为“辩控差”,辩方总分和控方总分之和称为“辩控和”。 简称为“辩控差” 辩方总分和控方总分之和称为“辩控和” 个候选人的辩方总分和控方总分之差记为V(i),辩方总分 第i 个候选人的辩方总分和控方总分之差记为 , 和控方总分之和记为S(i)。 和控方总分之和记为 。 现用f(j, k)表示,取j 个候选人,使其辩控差为 的所有方案 表示, 个候选人,使其辩控差为k 现用 表示 中 , 辩控和最大的那个方案(该方案称为“方案f(j, k)”)的 辩控和最大的那个方案( 该方案称为“ 方案 ) 辩控和。并且,我们还规定,如果没法选j 个人, 辩控和。并且,我们还规定,如果没法选 个人,使其辩控差 的值就为-1,也称方案f(j, k)不可行。 不可行。 为k,那么 ,那么f(j, k)的值就为 ,也称方案 的值就为 不可行 本题是要求选出m 个人,那么,如果对k 的所有可能的取值, 本题是要求选出 个人,那么,如果对 的所有可能的取值, 求出了所有的f(m, k) (-20×m≤ k ≤ 20×m),那么陪审团 求出了所有的 × × , 方案自然就很容易找到了。 方案自然就很容易找到了。

2、解题思路
问题的关键是建立递推关系。显然,方案f(j, k)是由某个可 问题的关键是建立递推关系。显然,方案 是由某个可 行的方案f(j-1, x)( -20×m ≤ x ≤ 20×m)演化而来的。 演化而来的。 行的方案 × × 演化而来的 可行方案f(j-1, x)能演化成方案 能演化成方案f(j, k)的必要条件是:存在 的必要条件是: 可行方案 能演化成方案 的必要条件是 某个候选人i, 在方案f(j-1, x)中没有被选上,且x+V(i) = k。 中没有被选上, 某个候选人 ,i 在方案 中没有被选上 。 在所有满足该必要条件的f(j-1, x)中,选出 f(j-1, x) + S(i) 在所有满足该必要条件的 中 的值最大的那个,那么方案f(j-1, x)再加上候选人 , 就演变 再加上候选人i, 的值最大的那个 , 那么方案 再加上候选人 成了方案 f(j, k)。 。 由上面知一个方案都选了哪些人需要全部记录下来。不妨将 由上面知一个方案都选了哪些人需要全部记录下来。不妨将 方案f(j, k)中最后选的那个候选人的编号,记在二维数组的元 中最后选的那个候选人的编号, 方案 中最后选的那个候选人的编号 的倒数第二个人选的编号, 素path[j][k]中。那么方案 中 那么方案f(j, k)的倒数第二个人选的编号, 的倒数第二个人选的编号 就是path[j-1][k-V[path[j][k]]]。 就是 。 假定最后算出了方案的辩控差是k,那么从path[m][k]出发, 出发, 假定最后算出了方案的辩控差是 ,那么从 出发 就能顺藤摸瓜一步步求出所有被选中的候选人。 就能顺藤摸瓜一步步求出所有被选中的候选人。

2、解题思路
初始条件,只能确定 初始条件,只能确定f(0, 0) = 0。由此出发,一步步自底向 。由此出发, 上递推,就能求出所有的可行方案f(m, k)( -20×m ≤ k ≤ 上递推,就能求出所有的可行方案 × 20×m)。 × 。 实际解题的时候,会用一个二维数组 来存放f(j, k)的值。而 的值。 实际解题的时候,会用一个二维数组f 来存放 的值 由于题目中辩控差的值k 可以为负数, 且,由于题目中辩控差的值 可以为负数,而程序中数租下标 不能为负数,所以,在程序中不妨将辩控差的值都加上 20×m, 以免下标为负数导致出错 , 即题目描述中 , 如果辩 × , 以免下标为负数导致出错, 即题目描述中, 控差为0,则在程序中辩控差为20× 。 控差为 ,则在程序中辩控差为 ×m。

3、参考程序
#include <stdio.h> #include <stdlib.h> #include <memory.h> int f[30][1000]; int Path[30][1000]; int P[300]; //控方打分 控方打分 int D[300]; //辩方打分 辩方打分 int Answer[30]; //存放最终方案的人选 存放最终方案的人选 int CompareInt(const void * e1, const void * e2) { return * ((int *) e1) - * ((int *) e2); }

int main(void) { int i, j, k; int t1, t2; int n, m; int nMinP_D; //辩控双方总分一样时的辩控差 辩控双方总分一样时的辩控差 int nCaseNo;//测试数据编号 测试数据编号 nCaseNo=0; scanf("%d%d", &n, &m); while(n+m) { nCaseNo++; for(i=1;i<=n;i++) scanf("%d%d", &P[i], &D[i]); memset(f, -1, sizeof(f)); memset(Path, 0, sizeof(Path)); nMinP_D=m*20; //题目中的辩控差为 题目中的辩控差为0 题目中的辩控差为 //对应到程序中辩控差就是 对应到程序中辩控差就是m*20 对应到程序中辩控差就是 f[0][nMinP_D]=0; //选0 个人辩控差为 的方案,其辩控和就是 选 个人辩控差为0 的方案,其辩控和就是0

3、参考程序

for(j=0;j<m;j++) { //每次循环选出第 个人,共要选出 人 每次循环选出第j 每次循环选出第 个人,共要选出m for(k=0;k<=nMinP_D*2;k++) //辩控差的范围是 辩控差的范围是[0, nMinP_D*2] 辩控差的范围是 { if(f[j][k]>=0) { //方案 f(j, k)可行 方案 可行 for(i=1;i<=n;i++) //由所有 由所有f(j, k),确定 由所有 ,确定f(j+1,*) { //*表示可能的辩控差 表示可能的辩控差 if(f[j][k]+P[i]+D[i]>f[j+1][k+P[i]-D[i]]) { //即时判别记住更合适的 即时判别记住更合适的f(j,k) 即时判别记住更合适的 t1=j; t2=k; while(t1>0&&Path[t1][t2]!=i) {//t2减去编号为 减去编号为Path[t1][t2]的辩控差 减去编号为 的辩控差 t2-=P[Path[t1][t2]]-D[Path[t1][t2]]; t1--;//减少 人 减少1人 减少 } if(t1==0) //没有发现 没有发现 { f[j+1][k+P[i]-D[i]]=f[j][k]+P[i]+D[i]; Path[j+1][k+P[i]-D[i]]=i; } } } } } }

3、参考程序

i=nMinP_D; j=0; while(f[m][i+j]<0&&f[m][i-j]<0)//从中间向左右同时找 从中间向左右同时找 j++; if(f[m][i+j]>f[m][i-j])//绝对值相同时找辩控和最大的 绝对值相同时找辩控和最大的 k=i+j; else k=i-j; printf("Jury #%d\n", nCaseNo); printf("Best jury has value %d for prosecution and value %d for defence:\n", (k-nMinP_D+f[m][k])/2, (f[m][k]-k+nMinP_D)/2); for(i=1;i<=m;i++) { Answer[i]=Path[m-i+1][k]; k-=P[Answer[i]]-D[Answer[i]];//减去辩控差 减去辩控差 } qsort(Answer+1, m, sizeof(int), CompareInt); for(i=1;i<=m;i++) printf(" %d", Answer[i]); printf("\n"); printf("\n"); scanf("%d%d", &n, &m);

3、参考程序

} return 0; }

购物问题
1、问题描述 、
由于换季, 商场推出优惠活动, 由于换季,ACM商场推出优惠活动,以超低价格出售 商场推出优惠活动 若干种商品。但是,商场为避免过分亏本, 若干种商品。但是,商场为避免过分亏本,规定某些 商品不能同时购买,而且每种超低价商品只能买一件。 商品不能同时购买,而且每种超低价商品只能买一件。 身为顾客的你想获得最大的实惠, 身为顾客的你想获得最大的实惠,也就是争取节省最 多的钱。经过仔细研究过,我们发现, 多的钱。经过仔细研究过,我们发现,商场出售的超 低价商品中,不存在以下这种情况: 低价商品中,不存在以下这种情况: N(3<=n)种商品 1,C2,…,Cn , 其中 i 和 Ci+1 是不能 种商品C 其中C 种商品 同时购买的(i=1,2,…,n-1),而且 1和Cn也不能同时 同时购买的 ,而且C 购买。 购买。 请编程计算可以节省的最大金额数。 请编程计算可以节省的最大金额数。

问题描述
输入数据
行两个整数K,M(1<=k<=1000),其中 表示超低价商品 第1行两个整数 行两个整数 ,其中K表示超低价商品 种商品的编号依次为1,2,…,K;M表示不能同时购买的 数 , K种商品的编号依次为 种商品的编号依次为 ; 表示不能同时购买的 商品对数。 商品对数。 接下来K行 行有一个整数X 接下来 行 , 第 i行有一个整数 i 表示购买编号为 的商品可以 行有一个整数 表示购买编号为i的商品可以 节省的金额(1<=Xi<=100)。 节省的金额 。 再接下来M行 每行两个数 和 ,表示A和 不能同时购买 不能同时购买, 再接下来 行,每行两个数A和B,表示 和B不能同时购买, 1<=A<=K,1<=B<=K,A≠B。 , , 。

输出要求 仅一个整数, 仅一个整数,表示能节省的最大金额数。

问题描述
输入样例
31 1 1 1 12

输出样例
2

2、解题思路
本题关键是构造一个结点带权的图, 本题关键是构造一个结点带权的图,结点表示超低 价商品,结点的权值表示购买该商品能节省的金额, 价商品,结点的权值表示购买该商品能节省的金额, 边表示边所连的两个点的商品不能同时购买。 边表示边所连的两个点的商品不能同时购买。这样就 相当于在图中找出一个点集, 相当于在图中找出一个点集,使该点集中任两点没有 连边而且权值之和最大。 连边而且权值之和最大。 依题意,该图是无环图,所以该图由若干棵树组成。 依题意,该图是无环图,所以该图由若干棵树组成。 只要把每棵树的相应最大节省金额求出来再求和即得 结果。 结果。

2、解题思路
对于单棵树,可以用动态规划的方法求出结果,方法如下: 对于单棵树,可以用动态规划的方法求出结果,方法如下: (1)对该棵树广度或深度遍历生成相应的有向树; 对该棵树广度或深度遍历生成相应的有向树; 对该棵树广度或深度遍历生成相应的有向树 (2)对树中每个结点定义两个函数 对树中每个结点定义两个函数F(i)和G(i),分别表示以 为 对树中每个结点定义两个函数 和 ,分别表示以i为 根的子树中选择i和不选择 和不选择i时 该子树的最大节省金额数。 根的子树中选择 和不选择 时,该子树的最大节省金额数。另 表示结点i权值 外S(i)表示结点 权值。动态规划方法为: 表示结点 权值。动态规划方法为: 对叶子结点: 对叶子结点:F(i)=S(i), G(i)=0 对非叶子结点: 对非叶子结点:F(i)=sum(G(j))+S(i), G(i)=sum(max(F(j),G(j))) 其中j为 的子女 的子女, 表示对各个子树求和。 其中 为i的子女,sum表示对各个子树求和。 表示对各个子树求和 (3)若该树的根为 ,则该树的结果为 若该树的根为r,则该树的结果为max(F(r),G(r))。 若该树的根为 。

#include<iostream> #include<string> using namespace std; int k, s[1001];//商品种类与其节省金额 商品种类与其节省金额 struct node //图结点定义 图结点定义 { node(int vv=0, node* nn=NULL) { v=vv; next=nn; } int v; node *next; } *g[1001];//g[i]表示第 个结点相邻的结点组成的链表 表示第i个结点相邻的结点组成的链表 表示第 int tag[1001];//标记结点是否搜索过没有 表示已搜索,0则没有 标记结点是否搜索过没有,1表示已搜索 标记结点是否搜索过没有 表示已搜索, 则没有 int funf[1001], fung[1001];//深度优先遍历该树并生成相应的有根树 深度优先遍历该树并生成相应的有根树 void search(int v);//搜索出以 为根生成的有根树 搜索出以 搜索出以v为根生成的有根树 int getf(int v);//计算以 为根的子树中选择 时,该子树的最大节省金额 计算以v为根的子树中选择 计算以 为根的子树中选择v时 数 int getg(int v);//计算以 为根的子树中不选择 时,该子树的最大节省 计算以v为根的子树中不选择 计算以 为根的子树中不选择v时 金额数

3、参考程序

3、参考程序
int main(void) { int m, i, v1, v2; int ans = 0; memset(g, 0, sizeof(g));//每个指针初始化为 每个指针初始化为NULL 每个指针初始化为 memset(tag, 0, sizeof(tag)); memset(funf,-1,sizeof(funf)); memset(fung,-1,sizeof(fung)); cin >> k >> m;//读入商品种类与不能同时购买商品对数 读入商品种类与不能同时购买商品对数 for(i=1; i<=k; i++)//读入各类节省金额 读入各类节省金额 cin >> s[i]; for(i=1; i<=m; i++)//读入不能同时购买商品对 读入不能同时购买商品对 { cin >> v1 >> v2; g[v1]=new node(v2,g[v1]);//以插入形成邻接表 以插入形成邻接表 g[v2]=new node(v1,g[v2]); }

3、参考程序
//对每个还没有被访问的结点,以该结点为根生成相应的有根树,对 对每个还没有被访问的结点,以该结点为根生成相应的有根树, 对每个还没有被访问的结点 //该树用动态规划的方法求解目标函数,并累加起来作为最终答案 该树用动态规划的方法求解目标函数, 该树用动态规划的方法求解目标函数 for(i=1; i<=k; i++) { if(tag[i] == 0) { search(i); ans += (getf(i) > getg(i) ? getf(i) : getg(i)); } } cout << ans; return 0; }

void search(int v)//搜索出以 为根生成的有根树 搜索出以v为根生成的有根树 搜索出以 {//关键是在邻接表中去掉回父结点的边 关键是在邻接表中去掉回父结点的边 tag[v]=1;//对每个相邻的结点 对每个相邻的结点 for(node* loop=g[v]; loop!=NULL; loop=loop->next)//对子女依次循环 对子女依次循环 { if(tag[loop->v] == 0)//该子女没有访问过 该子女没有访问过 { node *pre=NULL, *temp; for(temp=g[loop->v]; temp!=NULL; temp=temp->next) { if(temp->v == v) break;//邻结点是父亲,跳出 邻结点是父亲, 邻结点是父亲 pre=temp; } if(temp)//从break退出 从 退出 {//跳过可回到父亲的边 有根树,向下 跳过可回到父亲的边(有根树 跳过可回到父亲的边 有根树,向下) if(pre == NULL) g[loop->v] = g[loop->v]->next; else pre->next = temp->next; } search(loop->v);//深度搜索下一层 深度搜索下一层 } } }

3、参考程序

int getf(int v)//计算以 为根的子树中选择 时,该子树的最大节省金额 计算以v为根的子树中选择 计算以 为根的子树中选择v时 数 { if(funf[v] >= 0)//已经计算过 已经计算过 return funf[v]; funf[v] = s[v]; for(node *loop=g[v]; loop!=NULL; loop=loop->next) funf[v] += getg(loop->v);//逐个累加 不选子女 逐个累加(不选子女 逐个累加 不选子女) return funf[v]; } int getg(int v)//计算以 为根的子树中不选择 时,该子树的最大节省金 计算以i为根的子树中不选择 计算以 为根的子树中不选择i时 额数 { if(fung[v] >= 0) return fung[v]; fung[v] = 0; for(node* loop=g[v]; loop!=NULL; loop=loop->next) fung[v] += (getf(loop->v) > getg(loop->v) ? getf(loop->v) : getg(loop->v)); //判断子女选好还是不选好 判断子女选好还是不选好 return fung[v]; }

3、参考程序


赞助商链接
相关文章:
更多相关标签: