《动态规划的模型构建精.ppt》由会员分享，可在线阅读，更多相关《动态规划的模型构建精.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划的模型构建第1页，本讲稿共47页NOIP的动态规划试题的动态规划试题加分二叉树加分二叉树(2003)树型动态规划树型动态规划合唱队形合唱队形(2004)线型动态规划线型动态规划青蛙过河青蛙过河(2005)线型动态规划线型动态规划能量项链能量项链(2006)合并类型动态规划合并类型动态规划金明的预算方案金明的预算方案(2006)资源类型动态规划资源类型动态规划矩阵取数游戏矩阵取数游戏(2007)规则类型动态规划规则类型动态规划传纸条传纸条(2008)规则类型动态规划规则类型动态规划星球贸易星球贸易(2009)线型动态规划线型动态规划乌龟棋乌龟棋(2010)线型动态规划线型动态规划第2页，
2、本讲稿共47页引例：数字三角形引例：数字三角形如图所示的数字三角形中如图所示的数字三角形中 从第一行的数字出发从第一行的数字出发 每次向左下或右下走一格，直到最后一行每次向左下或右下走一格，直到最后一行 要求沿途数字之和最大要求沿途数字之和最大 1 3 2 4 10 1 4 3 2 20第3页，本讲稿共47页动态规划的基本概念动态规划的基本概念阶段：把问题分成几个相互联系的有顺序阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。的几个环节，这些环节即称为阶段。状态：某一阶段的出发位置称为状态。通状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。常一个阶段包含若干状态
3、。决策：从某阶段的一个状态演变到下一个决策：从某阶段的一个状态演变到下一个阶段某状态的选择。阶段某状态的选择。策略：由开始到终点的全过程中，由每段策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简决策组成的决策序列称为全过程策略，简称策略。称策略。第4页，本讲稿共47页动态规划的基本概念动态规划的基本概念状态转移方程：前一阶段的终点就是后一状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由后一阶段的状态，这种关系描述了由k阶段阶段到到k+1阶段状态的演变规律，称为状态转移阶段状态的演
4、变规律，称为状态转移方程。方程。目标函数与最优化概念：目标函数是衡量目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程目具体性质所确定的运算以后，使全过程的总效益达到最优。的总效益达到最优。第5页，本讲稿共47页最优化原理一个最优化策略具有这样的性质，不论过一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优的状态而言，余下的诸决策必须构成
5、最优策略。策略。简而言之，一个最优化策略的子策略总是简而言之，一个最优化策略的子策略总是最优的。最优的。最优化原理是动态规划的基础，任何问题，最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能如果失去了最优化原理的支持，就不可能用动态规划方法计算。用动态规划方法计算。第6页，本讲稿共47页无后效性“过去的步骤只能通过当前状态影响未来的过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结发展，当前的状态是历史的总结”。这条。这条特征说明动态规划只适用于解决当前决策特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策与过去状态无关的问题。状态
6、，出现在策略任何一个位置，它的地位相同，都可实略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。施同样策略，这就是无后效性的内涵。举例举例最短路（不带负权边，带负权边）最短路（不带负权边，带负权边）第7页，本讲稿共47页动态规划的解题步骤动态规划的解题步骤划分阶段：注意阶段一定要是有序的或者划分阶段：注意阶段一定要是有序的或者是可排序的，否则问题就无法求解。是可排序的，否则问题就无法求解。选择状态：状态的选择要满足无后效性。选择状态：状态的选择要满足无后效性。确定决策：决策决定着状态的转移，状态确定决策：决策决定着状态的转移，状态转移就是根据上一阶段的状态和决策来导转移就是
7、根据上一阶段的状态和决策来导出本阶段的状态。出本阶段的状态。写出状态转移方程（包括边界条件和取值写出状态转移方程（包括边界条件和取值范围）：根据问题的性质（求最大范围）：根据问题的性质（求最大/最小），最小），用数学方程描述状态转移的方法和过程用数学方程描述状态转移的方法和过程第8页，本讲稿共47页编程实现？循环循环For i For j (dummy)递归递归Solve(i,j)If solved fij return fij(dummy)第9页，本讲稿共47页数字三角形求解状态：状态：f(i,j)表示走到第表示走到第i行行j列获得的最大值列获得的最大值状态转移方程状态转移方程:f(i,j)
8、=maxf(i-1,j),f(i-1,j+1)+ai,j 初始：初始：f(0,0)=0第10页，本讲稿共47页问题问题1：求最短距离（：求最短距离（1）某人要从某人要从S1前往前往SN，其中，其中Si至至Si+1有若干种行有若干种行进方式（步行，自行车，公交车，越野车，进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间），分别要花费一定的时间问最快到达的时间是多少？问最快到达的时间是多少？第11页，本讲稿共47页分析分析划分阶段、选择状态：到达各个不同的地点作为一个阶段 一个阶段里就一个状态 用Fi表示从S1到达Si所需最短的时间 写出规划方程（包括边界条件）：F1=0 Fi
9、=Fi-1+Si-1到达Si所需花费的最短时间第12页，本讲稿共47页问题问题1：求最短距离（：求最短距离（2）某人要从某人要从S1前往前往SN，其中，其中Si至至Si+1有若干种行有若干种行进方式（步行，自行车，公交车，越野车，进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间，并且如果），分别要花费一定的时间，并且如果在一个地点选择切换行进方式，需要额外在一个地点选择切换行进方式，需要额外消耗一定的时间。消耗一定的时间。问最快到达的时间是多少？问最快到达的时间是多少？第13页，本讲稿共47页分析划分阶段、选择状态：划分阶段、选择状态：使用与上面一样的方案发现不可行，无法使
10、用与上面一样的方案发现不可行，无法解决判定是否需要切换行进方式解决判定是否需要切换行进方式 加一维状态进行表示加一维状态进行表示 用用fij表示要从表示要从S1到达到达Si，在，在Si时使用的出时使用的出行方式为行方式为j，所需最短的时间，所需最短的时间写出规划方程（包括边界条件）写出规划方程（包括边界条件）第14页，本讲稿共47页思考？思考？必须在每个地点切换行进方式？必须在每个地点切换行进方式？“Si至至Si+1有若干种行进方式有若干种行进方式”为为“Si至至Sj(ji)有若干有若干种行进方式种行进方式”？若为任意两点若为任意两点Si至至Sj之间都有若干种行进方式？之间都有若干种行进方式？
11、若在切换时候需要行进方式时须增加时间？若在切换时候需要行进方式时须增加时间？中途经过的地点不能超过中途经过的地点不能超过X个，该如何处理？个，该如何处理？若费用为负怎么办？若费用为负怎么办？第15页，本讲稿共47页分析设设f(i)表示前表示前i个数的最长不上升序列的长度。个数的最长不上升序列的长度。则则,f(i)=maxf(j)+1,其中其中j=ai这里这里0ji=n。显然时间复杂度为显然时间复杂度为O(n2)。上述式子的含义：找到上述式子的含义：找到i之前的某之前的某j，这个数，这个数不比第不比第i个数小个数小,对于所有的对于所有的j取取f(j)的最大值。的最大值。第16页，本讲稿共47页问
12、题问题2:求最长公共子序列求最长公共子序列给定的字符序列给定的字符序列X=“x0，x1，xm-1”，序列序列Y=“y0，y1，yk-1”是是X的子序列，存在的子序列，存在X的一个严格递增下标序的一个严格递增下标序列列，使得对所有的，使得对所有的j=0，1，k-1，有有xij=yj。例如，例如，X=“ABCBDAB”，Y=“BCDB”是是X的一个子序的一个子序列。列。给出两个字串给出两个字串S1和和S2，长度不超过，长度不超过5000.求这两个串的最长公共子序列长度。求这两个串的最长公共子序列长度。第17页，本讲稿共47页动态规划设设f(i,j)表示表示S的前的前i位与位与T的前的前j位的最长公
13、共子串长度。则有，位的最长公共子串长度。则有，时间复杂度时间复杂度O(n*m)第18页，本讲稿共47页思考？思考？给出两个串，求最长公共子串？给出两个串，求最长公共子串？给定两个字符串，求最小编辑次数使得两给定两个字符串，求最小编辑次数使得两个字符串相等，所谓编辑，即删除、插入个字符串相等，所谓编辑，即删除、插入或修改某个字符。或修改某个字符。给出一个串，求最小编辑次数，使得某个给出一个串，求最小编辑次数，使得某个串变成回文串？串变成回文串？第19页，本讲稿共47页问题问题3：01背包问题背包问题有有N件物品件物品;第第i件物品件物品Wi公斤公斤;第第i件物品价值件物品价值Ci元元;现有一辆载
14、重现有一辆载重M公斤的卡车公斤的卡车;问选取装载哪些物品，使得卡车运送的问选取装载哪些物品，使得卡车运送的总价值最大？总价值最大？第20页，本讲稿共47页动态规划可以按每个物品进行规划，同样每种物品有选和不选两种选择设F(i,j)表示前i件物品载重为j的最大效益，则有1=i=N,0=j=N初值：初值：F(0,j)=0F(N,M)即答案显然时间复杂度为O(NM)第21页，本讲稿共47页思考？思考？完全背包问题：即每个物品可取无限次。完全背包问题：即每个物品可取无限次。多重背包问题：第多重背包问题：第i种物品可取种物品可取ni次。次。带条件背包问题：取某种物品，必须取另带条件背包问题：取某种物品，
15、必须取另外一种物品的限制。外一种物品的限制。二维背包问题：物品分为两类，每类分别二维背包问题：物品分为两类，每类分别放到一个背包中。放到一个背包中。每个物品有个编号，价值最大的前提下，每个物品有个编号，价值最大的前提下，所取物品组成的排列字典序最小。所取物品组成的排列字典序最小。第22页，本讲稿共47页问题问题4：石子合并：石子合并 在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(
16、2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据:第一行为石子堆数N;第二行为每堆石子数,每两个数之间用一空格分隔.输出数据:从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.第23页，本讲稿共47页示例第24页，本讲稿共47页N=5 石子数分别为3 4 6 5 4 2。用贪心法的合并过程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次3 4 6 5 4 2得分 7
17、第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24总分：61显然，贪心法是错误的。第25页，本讲稿共47页动态规划动态规划 用用datai,jdatai,j表示将从第表示将从第i i颗石子开始的接下来颗石子开始的接下来j j颗石子合并所得的分颗石子合并所得的分值，值，maxi,jmaxi,j表示将从第表示将从第i i颗石子开始的接下来颗石子开始的接下来j j颗石子合并可能的最大颗石子合并可能的最大值，那么：值，那么：maxi,j=max(maxi,k+maxi+k,j maxi,j=max(maxi,k+maxi+k,j
18、k+k+datai,k+datai+k,jdatai,k+datai+k,jk)(2=k=j)k)(2=k=j)maxi,i=0maxi,i=0同样的，我们用同样的，我们用mini,jmini,j表示将第从第表示将第从第i i颗石子开始的接下来颗石子开始的接下来j j颗颗石子合并所得的最小值，可以得到类似的方程：石子合并所得的最小值，可以得到类似的方程：mini,j=min(mini,k+mini+k,j mini,j=min(mini,k+mini+k,j k+datai,k+k+datai,k+datai+k,jdatai+k,j k)(0=k=j)k)(0=k=j)mini,i=0min
19、i,i=0这样，我们完美地解决了这道题。时间复杂度也是这样，我们完美地解决了这道题。时间复杂度也是O(nO(n3 3)。第26页，本讲稿共47页思考题：多边形思考题：多边形 多多角角形形是是一一个个单单人人玩玩的的游游戏戏，开开始始时时有有一一个个N N个个顶顶点点的的多多边边形形。如如图图，这这里里N=4N=4。每每个个顶顶点点有有一一个个整整数数标标记记，每每条条边边上上有有一一个个“+”号号或或“*”号号。边边从从1 1编编号号到到N N。第第一一步步，一一条条边边被被拿拿走走；随随后后各各步步包包括如下：括如下：选选择择一一条条边边E E和和连连接接着着E E的的两两个个顶顶点点V1V
20、1和和 V2V2；得得到到一一个个新新的的顶顶点点，标标记记为为V1V1与与V2V2通通过过边边E E上的运算符运算的结果。上的运算符运算的结果。最最后后，游游戏戏中中没没有有边边，游游戏戏的的得得分分为为仅剩余的一个顶点的值。仅剩余的一个顶点的值。第27页，本讲稿共47页样例写一个程序，写一个程序，对对于于给给定一个多定一个多边边形，形，计计算出可能的最高算出可能的最高得分，并且列出得到得分，并且列出得到这这个分数的个分数的过过程。程。第28页，本讲稿共47页问题问题5：Robots 在一个在一个n*m的棋盘内，一些格子里有垃圾要的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从
21、左拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内每次他到达一个点，就会自动把这个点内的垃圾拾掉。的垃圾拾掉。问：最多能拾多少垃圾。在最多的情况下，问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。有多少种方案？请举出一种方案来。数据范围数据范围:n=100,m=100第29页，本讲稿共47页举例最多能拾5块。有4种方法。第30页，本讲稿共47页分析：因为只能向右或者向下走。也就是说不能走回头路。于是考虑动态规划。设Fi,j表示从(1,1)点开始走到(i,j)的时候，最多捡了
22、多少垃圾。Gi,j表示在fi,j最大的时候，有多少种方案。Ci,j=1表示(i,j)点有垃圾。Ci,j=0表示没有。第31页，本讲稿共47页状态转移方程根据(i,j)只能从(i-1,j)或者(i,j-1)走过来。于是fi,j=Maxfi-1,j,fi,j-1+ci,j.怎么求g(i,j)？可变成有向无环图来解决。可变成有向无环图来解决。第32页，本讲稿共47页思考？两个机器人同时捡垃圾，如何处理？两个机器人同时捡垃圾，如何处理？三个机器人呢？三个机器人呢？若某些垃圾之间有联系，必须同时拾捡？若某些垃圾之间有联系，必须同时拾捡？第33页，本讲稿共47页免费馅饼免费馅饼 SERKOISERKOI最
23、新推出了一种叫做最新推出了一种叫做“免费馅饼免费馅饼”的游戏。的游戏。游戏在一个舞台上进行。舞台的宽度为游戏在一个舞台上进行。舞台的宽度为W W格，天幕的高度为格，天幕的高度为H H格，格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。着一个托盘。游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。一格或两格，也可以站在愿地不动。馅
24、饼有很多种，游戏者事先根据自己的口味，对各种馅饼依馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在次打了分。同时在8-3088-308电脑的遥控下，各种馅饼下落的速度也是电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。戏者所在的格子中，游戏者就收集到了这块馅饼。写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。和最大。第34页，本讲稿共47页输入数据
25、：输入数据：第一行第一行:宽度宽度W（199奇数）和高度奇数）和高度H（1 100整数）整数）接下来给出了一块馅饼信息。由接下来给出了一块馅饼信息。由4个正整数组成，分别表示了馅饼的个正整数组成，分别表示了馅饼的初始下落时刻、水平位置、下落速度、分值。初始下落时刻、水平位置、下落速度、分值。游戏开始时刻为游戏开始时刻为0。从。从1开始自左向右依次对水平方向的每格编开始自左向右依次对水平方向的每格编号。号。输出数据：输出数据：收集到的馅饼最大分数之和。收集到的馅饼最大分数之和。第35页，本讲稿共47页由上图可知，尽管下落了由上图可知，尽管下落了4个馅饼，但只能接到个馅饼，但只能接到3个：个：第第
26、1时刻可以接到分值为时刻可以接到分值为5的馅饼的馅饼第第2时刻可以接到分值为时刻可以接到分值为3的馅饼的馅饼第第3时刻可以接到分值为时刻可以接到分值为4的馅饼的馅饼因此馅饼的总分值为因此馅饼的总分值为5+3+4=12第36页，本讲稿共47页问题问题6：加分二叉树：加分二叉树给定一个中序遍历为给定一个中序遍历为1,2,3,n的二叉树的二叉树每个结点有一个权值每个结点有一个权值定义二叉树的加分规则为：定义二叉树的加分规则为：左子树的加分左子树的加分 右子树的加分根的分数右子树的加分根的分数若某个树缺少左子树或右子树，规定缺少的子若某个树缺少左子树或右子树，规定缺少的子树加分为树加分为1。构造符合条
27、件的二叉树构造符合条件的二叉树该树加分最大该树加分最大输出其前序遍历序列输出其前序遍历序列第37页，本讲稿共47页样例样例中序遍历为中序遍历为1,2,3,4,5的二叉树有很多，下图的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为是其中的三棵，其中第三棵加分最大，为145.第38页，本讲稿共47页分析性质：中序遍历是按性质：中序遍历是按“左左-根根-右右”方式进行遍历二叉树，因此二叉方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！根结点的右边！因此，假设二叉树的根结点为因此，假设二叉
28、树的根结点为k，那么中序遍历为，那么中序遍历为1,2,n的遍历序的遍历序列，左孩子序列为列，左孩子序列为1,2,k-1，右孩子序列为，右孩子序列为k+1,k+2,n，如下图，如下图第39页，本讲稿共47页动态规划设设f(i,j)中序遍历为中序遍历为i,i+1,j的二叉树的最大加分，则有：的二叉树的最大加分，则有：f(i,j)=maxfi,k-1*fk+1,j+dk显然显然 f(i,i)=di答案为答案为f(1,n)1=i=k=j=n时间复杂度时间复杂度 O(n3)要构造这个树，只需记录每次的决策值，令要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示，表示中序遍历为中序遍历为i,i+
29、1,j的二叉树的取最优决策时的根结点的二叉树的取最优决策时的根结点为为k最后前序遍历这个树即可。最后前序遍历这个树即可。第40页，本讲稿共47页思考题：选课思考题：选课 大大学学里里实实行行学学分分。每每门门课课程程都都有有一一定定的的学学分分，学学生生只只要要选选修修了了这这门门课课并并考考核核通通过过就就能能获获得得相相应应的的学学分分。学学生生最最后后的的学学分分是是他他选选修修的的各各门课的学分的总和。门课的学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一选修，有些课
30、程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，些课程的基础上才能选修。例如，数据结构数据结构必须在选修了必须在选修了高级语言程序设计高级语言程序设计之后才能选修。我们称之后才能选修。我们称高级语言程序高级语言程序设计设计是是数据结构数据结构的先修课。每门课的直接先修课最多只的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为有一个课号，课号依次为1 1，2 2，3 3，。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，每个学生可选课程的总数是给定
31、的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。课程之间不存在时间上的冲突。第41页，本讲稿共47页 输入输入 输输入入文文件件的的第第一一行行包包括括两两个个正正整整数数M M、N N（中中间间用用一一个个空空格格隔隔开开）其其中中M M表表示示待待选选课课程程总总数数（1M1000)1M1000)，N N表表示示学学生生可可以以选选的的课程总数（课程总数（1NM)1NM)。以以下下M M行行每每行行代代表表一一门门课课，课课号号依依次次为为1 1，2 2M M。每每行行
32、有有两两个个数数（用用一一个个空空格格隔隔开开），第第一一个个数数为为这这门门课课的的先先修修课课的的课课号号（若若不不存存在在先先修修课课则则该该项项为为0 0），第第二二个个数数为为这这门门课课的的学学分分。学学分是不超过分是不超过1010的正整数。的正整数。输出输出 输输出出文文件件第第一一行行只只有有一一个个数数，即即实实际际所所选选课课程程的的学学分分总总数数。以下以下N N行每行有一个数，表示学生所选课程的课号。行每行有一个数，表示学生所选课程的课号。第42页，本讲稿共47页问题问题7：聚会的快乐：聚会的快乐你要组织一个由你公司的人参加的聚会。你希望聚会非常愉你要组织一个由你公司的
33、人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定个人和他的上司，因为这可能带来争吵。给定N个人个人(姓名，姓名，他幽默的系数，以及他上司的名字他幽默的系数，以及他上司的名字)，编程找到能使幽默系数和最，编程找到能使幽默系数和最大的若干个人。大的若干个人。【输入输入】第一行一个整数第一行一个整数N(N100)。接下来有。接下来有N行，每一行描述一个人的行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过信息，信息之间用空格隔开。姓名是长度不超过20的字符串，的
34、字符串，幽默系数是在幽默系数是在0到到100之间的整数。之间的整数。【输出输出】所邀请的人最大的幽默系数和。所邀请的人最大的幽默系数和。第43页，本讲稿共47页样例【样例样例】party.in party.out58BART 1 HOMERHOMER 2 MONTGOMERYMONTGOMERY 1 NOBODYLISA 3 HOMERSMITHERS 4 MONTGOMERY第44页，本讲稿共47页分析 首先，很显然公司的人员关系构成了一棵树。设首先，很显然公司的人员关系构成了一棵树。设fa为为a参参加会议的情况下，以他为根的子树取得的最大幽默值；加会议的情况下，以他为根的子树取得的最大幽默
35、值；ga为为a不参加会议的情况下，以他为根的子树取得的不参加会议的情况下，以他为根的子树取得的最大幽默值。那么，状态转移方程就是：最大幽默值。那么，状态转移方程就是：fa=gb1+gb2+gbk+1ga=max(fb1,gb1)+max(fb2,gb2)+max(fbk,gbk)其中其中b1,b2,bk为为a的子结点。的子结点。最后的答案就是最后的答案就是max(froot,groot)，root是树是树第45页，本讲稿共47页思考题：警卫安排思考题：警卫安排一个有一个有N个区域的树结构上需要安排若干个警卫；个区域的树结构上需要安排若干个警卫；每个区域安排警卫所需要的费用是不同的；每个区域安排警卫所需要的费用是不同的；每个区域的警卫都可以望见其相邻的区域，只要一个区域每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；被一个警卫望见或者是安排有警卫，这个区域就是安全的；任务：在确保所有区域都是安全的情况下，找到安排任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；警卫的最小费用；0n=720；第46页，本讲稿共47页联系方式长沙市雅礼中学 朱全民 410007第47页，本讲稿共47页