[计算机]动态规划的模型构建课件.ppt

1、动态规划的模型构建动态规划的模型构建长沙市雅礼中学长沙市雅礼中学 朱全民朱全民NOIP的动态规划试题的动态规划试题 加分二叉树加分二叉树(2003)树型动态规划树型动态规划 合唱队形合唱队形(2004)线型动态规划线型动态规划 青蛙过河青蛙过河(2005)线型动态规划线型动态规划 能量项链能量项链(2006)合并类型动态规划合并类型动态规划 金明的预算方案金明的预算方案(2006)资源类型动态规划资源类型动态规划 矩阵取数游戏矩阵取数游戏(2007)规则类型动态规划规则类型动态规划 传纸条传纸条(2008)规则类型动态规划规则类型动态规划 星球贸易星球贸易(2009)线型动态规划线型动态规划

2、乌龟棋乌龟棋(2010)线型动态规划线型动态规划引例：数字三角形引例：数字三角形如图所示的数字三角形中如图所示的数字三角形中 从第一行的数字出发从第一行的数字出发 每次向左下或右下走一格，直到最后一行每次向左下或右下走一格，直到最后一行 要求沿途数字之和最大要求沿途数字之和最大 1 3 2 4 10 1 4 3 2 20动态规划的基本概念动态规划的基本概念 阶段：把问题分成几个相互联系的有顺序阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。的几个环节，这些环节即称为阶段。状态：某一阶段的出发位置称为状态。通状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。常一个阶

3、段包含若干状态。决策：从某阶段的一个状态演变到下一个决策：从某阶段的一个状态演变到下一个阶段某状态的选择。阶段某状态的选择。策略：由开始到终点的全过程中，由每段策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简决策组成的决策序列称为全过程策略，简称策略。称策略。动态规划的基本概念动态规划的基本概念 状态转移方程：前一阶段的终点就是后一状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由后一阶段的状态，这种关系描述了由k阶阶段到段到k+1阶段状态的演变规律，称为状态阶段状态的演变规律，称

4、为状态转移方程。转移方程。目标函数与最优化概念：目标函数是衡量目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程目具体性质所确定的运算以后，使全过程的总效益达到最优。的总效益达到最优。最优化原理 一个最优化策略具有这样的性质，不论过一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优的状态而言，余下的诸决策必须构成最优策略。策略。简而言之，

5、一个最优化策略的子策略总是简而言之，一个最优化策略的子策略总是最优的。最优的。最优化原理是动态规划的基础，任何问题最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可，如果失去了最优化原理的支持，就不可能用动态规划方法计算。能用动态规划方法计算。无后效性“过去的步骤只能通过当前状态影响未来的过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结发展，当前的状态是历史的总结”。这条。这条特征说明动态规划只适用于解决当前决策特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实略

6、任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。施同样策略，这就是无后效性的内涵。举例举例 最短路（不带负权边，带负权边）最短路（不带负权边，带负权边）动态规划的解题步骤动态规划的解题步骤 划分阶段：注意阶段一定要是有序的或者划分阶段：注意阶段一定要是有序的或者是可排序的，否则问题就无法求解。是可排序的，否则问题就无法求解。选择状态：状态的选择要满足无后效性。选择状态：状态的选择要满足无后效性。确定决策：决策决定着状态的转移，状态确定决策：决策决定着状态的转移，状态转移就是根据上一阶段的状态和决策来导转移就是根据上一阶段的状态和决策来导出本阶段的状态。出本阶段的状态。写出状

7、态转移方程（包括边界条件和取值写出状态转移方程（包括边界条件和取值范围）：根据问题的性质（求最大范围）：根据问题的性质（求最大/最小）最小），用数学方程描述状态转移的方法和过程，用数学方程描述状态转移的方法和过程编程实现？循环循环 For i For j (dummy)递归递归 Solve(i,j)If solved fij return fij(dummy)数字三角形求解 状态：状态：f(i,j)表示走到第表示走到第i行行j列获得的最大值列获得的最大值 状态转移方程状态转移方程:f(i,j)=maxf(i-1,j),f(i-1,j+1)+ai,j 初始：初始：f(0,0)=0问题问题1：求最

8、短距离（：求最短距离（1）某人要从某人要从S1前往前往SN，其中，其中Si至至Si+1有若干种行有若干种行进方式（步行，自行车，公交车，越野车进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间），分别要花费一定的时间 问最快到达的时间是多少？问最快到达的时间是多少？分析分析 划分阶段、选择状态：到达各个不同的地点作为一个阶段 一个阶段里就一个状态 用Fi表示从S1到达Si所需最短的时间 写出规划方程（包括边界条件）：F1=0 Fi=Fi-1+Si-1到达Si所需花费的最短时间问题问题1：求最短距离（：求最短距离（2）某人要从某人要从S1前往前往SN，其中，其中Si至至Si+1

9、有若干种行有若干种行进方式（步行，自行车，公交车，越野车进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间，并且如），分别要花费一定的时间，并且如果在一个地点选择切换行进方式，需要额果在一个地点选择切换行进方式，需要额外消耗一定的时间。外消耗一定的时间。问最快到达的时间是多少？问最快到达的时间是多少？分析 划分阶段、选择状态：划分阶段、选择状态：使用与上面一样的方案发现不可行，无法使用与上面一样的方案发现不可行，无法解决判定是否需要切换行进方式解决判定是否需要切换行进方式 加一维状态进行表示加一维状态进行表示 用用fij表示要从表示要从S1到达到达Si，在，在Si时使用的出时

10、使用的出行方式为行方式为j，所需最短的时间，所需最短的时间 写出规划方程（包括边界条件）写出规划方程（包括边界条件）思考？思考？必须在每个地点切换行进方式？必须在每个地点切换行进方式？“Si至至Si+1有若干种行进方式有若干种行进方式”为为“Si至至Sj(ji)有有若干种行进方式若干种行进方式”？若为任意两点若为任意两点Si至至Sj之间都有若干种行进方式？之间都有若干种行进方式？若在切换时候需要行进方式时须增加时间？若在切换时候需要行进方式时须增加时间？中途经过的地点不能超过中途经过的地点不能超过X个，该如何处理？个，该如何处理？若费用为负怎么办？若费用为负怎么办？分析 设设f(i)表示前表示

11、前i个数的最长不上升序列的长度。个数的最长不上升序列的长度。则则,f(i)=maxf(j)+1,其中其中j=ai这里这里0ji=n。显然时间复杂度为显然时间复杂度为O(n2)。上述式子的含义：找到上述式子的含义：找到i之前的某之前的某j，这个数，这个数不比第不比第i个数小个数小,对于所有的对于所有的j取取f(j)的最大值。的最大值。问题问题2:求最长公共子序列求最长公共子序列 给定的字符序列给定的字符序列X=“x0，x1，xm-1”，序列序列Y=“y0，y1，yk-1”是是X的子序列，存在的子序列，存在X的一个的一个严格递增下标序列严格递增下标序列，使得对所有，使得对所有的的j=0，1，k-1

12、，有，有xij=yj。例如，例如，X=“ABCBDAB”，Y=“BCDB”是是X的一个的一个子序列。子序列。给出两个字串给出两个字串S1和和S2，长度不超过，长度不超过5000.求这两个串的最长公共子序列长度。求这两个串的最长公共子序列长度。动态规划 设设f(i,j)表示表示S的前的前i位与位与T的前的前j位的最长公共子串长度。则位的最长公共子串长度。则有，有，时间复杂度时间复杂度O(n*m)jijitsjijiftsjijifjifjijif&0,1)1,1(&0,),1(),1,(max0|0,0),(当当当思考？思考？给出两个串，求最长公共子串？给出两个串，求最长公共子串？给定两个字符串

13、，求最小编辑次数使得两给定两个字符串，求最小编辑次数使得两个字符串相等，所谓编辑，即删除、插入个字符串相等，所谓编辑，即删除、插入或修改某个字符。或修改某个字符。给出一个串，求最小编辑次数，使得某个给出一个串，求最小编辑次数，使得某个串变成回文串？串变成回文串？问题问题3：01背包问题背包问题 有有N件物品件物品;第第i件物品件物品Wi公斤公斤;第第i件物品价值件物品价值Ci元元;现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;问选取装载哪些物品，使得卡车运送的问选取装载哪些物品，使得卡车运送的总价值最大？总价值最大？动态规划 可以按每个物品进行规划，同样每种物品有选和不选两种选择 设F(i,

14、j)表示前i件物品载重为j的最大效益，则有 1=i=N,0=j=N 初值：初值：F(0,j)=0 F(N,M)即答案 显然时间复杂度为O(NM)种物品不装载第种物品装载第ijiFiiCiwjiFMaxjiF),1(,),1(),(思考？思考？完全背包问题：即每个物品可取无限次。完全背包问题：即每个物品可取无限次。多重背包问题：第多重背包问题：第i种物品可取种物品可取ni次。次。带条件背包问题：取某种物品，必须取另带条件背包问题：取某种物品，必须取另外一种物品的限制。外一种物品的限制。二维背包问题：物品分为两类，每类分别二维背包问题：物品分为两类，每类分别放到一个背包中。放到一个背包中。每个物品

15、有个编号，价值最大的前提下，每个物品有个编号，价值最大的前提下，所取物品组成的排列字典序最小。所取物品组成的排列字典序最小。问题问题4：石子合并：石子合并 在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大 输入数据:第一行为石子堆数N;第二行为每堆石子数,每两个数之间用一空格分隔.输出数据:从第1至第N行为得分最小的合并

16、方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.示例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第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24总分：61显然，贪心法是错误的。动态规划动态规划 用用datai,jdatai,j 表示将从第表示将从第

17、i i颗石子开始的接下来颗石子开始的接下来j j颗石子合颗石子合并所得的分值，并所得的分值，maxi,jmaxi,j 表示将从第表示将从第i i颗石子开始的接下来颗石子开始的接下来j j颗石子合并可颗石子合并可能的最大值，那么：能的最大值，那么：maxi,jmaxi,j=max(maximax(maxi,k+,k+maximaxi+k,j +k,j k+k+datai,kdatai,k+datai+kdatai+k,j,jk)(2=k=j)k)(2=k=j)maxi,imaxi,i=0=0 同样的，我们用同样的，我们用mini,jmini,j 表示将第从第表示将第从第i i颗石子开始的接颗石子

18、开始的接下来下来j j颗石子合并所得的最小值，可以得到类似的方程：颗石子合并所得的最小值，可以得到类似的方程：mini,jmini,j=min(minimin(mini,k+,k+minimini+k,j +k,j k+k+datai,kdatai,k+datai+kdatai+k,j,j k)(0=k=j)k)(0=k=j)mini,imini,i=0=0 这样，我们完美地解决了这道题。时间复杂度也是这样，我们完美地解决了这道题。时间复杂度也是O(nO(n3 3)。思考题：多边形思考题：多边形 多角形是一个单人玩的游戏，开多角形是一个单人玩的游戏，开始时有一个始时有一个N N个顶点的多边形。

19、如个顶点的多边形。如图，这里图，这里N=4N=4。每个顶点有一个整。每个顶点有一个整数标记，每条边上有一个数标记，每条边上有一个“+”号或号或“*”号。边从号。边从1 1编号到编号到N N。第一步，一条边被拿走；随后各步第一步，一条边被拿走；随后各步包括如下：包括如下：选择一条边选择一条边E E和连接着和连接着E E的两个顶的两个顶点点V1V1和和 V2V2；得到一个新的顶点，标记为得到一个新的顶点，标记为V1V1与与V2V2通过边通过边E E上的运算符运算的结果。上的运算符运算的结果。最后，游戏中没有边，游戏的得最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。分为仅剩余的一个顶点的值。

20、-7425+*1234+*样例-7 4 2 5+*1 2 4+42+*24-24+2-40写一个程序，对于给定一个多边形，计算出可能写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。的最高得分，并且列出得到这个分数的过程。问题问题5：Robots 在一个在一个n*m的棋盘内，一些格子里有垃圾要的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内每次他到达一个点，就会自动把这个点内的垃圾拾掉。的垃圾拾掉。问

21、：最多能拾多少垃圾。在最多的情况下，问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。有多少种方案？请举出一种方案来。数据范围数据范围:n=100,m=100举例 最多能拾5块。有4种方法。分析：因为只能向右或者向下走。也就是说不能走回头路。于是考虑动态规划。设Fi,j表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。Gi,j表示在fi,j最大的时候，有多少种方案。Ci,j=1表示(i,j)点有垃圾。Ci,j=0表示没有。状态转移方程 根据(i,j)只能从(i-1,j)或者(i,j-1)走过来。于是fi,j=Maxfi-1,j,fi,j-1+ci,j.怎么求g(

22、i,j)？可变成有向无环图来解决。可变成有向无环图来解决。思考？两个机器人同时捡垃圾，如何处理？两个机器人同时捡垃圾，如何处理？三个机器人呢？三个机器人呢？若某些垃圾之间有联系，必须同时拾捡？若某些垃圾之间有联系，必须同时拾捡？免费馅饼免费馅饼 SERKOISERKOI最新推出了一种叫做最新推出了一种叫做“免费馅饼免费馅饼”的游戏。的游戏。游戏在一个舞台上进行。舞台的宽度为游戏在一个舞台上进行。舞台的宽度为W W格，天幕的高度格，天幕的高度为为H H格，游戏者占一格。开始时，游戏者站在舞台的正中格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。央，手里拿着一个托盘。游戏开始后

23、，从舞台天幕顶端的格子中不断出现馅饼并游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。向左或右移动一格或两格，也可以站在愿地不动。馅饼有很多种，游戏者事先根据自己的口味，对各种馅馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在饼依次打了分。同时在8-3088-308电脑的遥控下，各种馅饼下电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格落的速度也是不一样的，下落速度以格/秒为单位。当馅秒为单位。当馅饼在某一秒末恰好到达游戏者所

24、在的格子中，游戏者就饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。收集到了这块馅饼。写一个程序，帮助我们的游戏者收集馅饼，使得收集的写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。馅饼的分数之和最大。输入数据：输入数据：第一行第一行:宽度宽度W（199奇数）和高度奇数）和高度H（1 100整数）整数）接下来给出了一块馅饼信息。由接下来给出了一块馅饼信息。由4个正整数组成，分别表个正整数组成，分别表示了馅饼的示了馅饼的初始下落时刻、水平位置、下落速度、分值。初始下落时刻、水平位置、下落速度、分值。游戏开始时刻为游戏开始时刻为0。从。从1开始自左向右依次对水

25、平方向的每开始自左向右依次对水平方向的每格编号。格编号。输出数据：输出数据：收集到的馅饼最大分数之和。收集到的馅饼最大分数之和。由上图可知，尽管下落了由上图可知，尽管下落了4个馅饼，但只能接到个馅饼，但只能接到3个：个：第第1时刻可以接到分值为时刻可以接到分值为5的馅饼的馅饼 第第2时刻可以接到分值为时刻可以接到分值为3的馅饼的馅饼 第第3时刻可以接到分值为时刻可以接到分值为4的馅饼的馅饼 因此馅饼的总分值为因此馅饼的总分值为5+3+4=12问题问题6：加分二叉树：加分二叉树 给定一个中序遍历为给定一个中序遍历为1,2,3,n的二叉树的二叉树 每个结点有一个权值每个结点有一个权值 定义二叉树的

26、加分规则为：定义二叉树的加分规则为：左子树的加分左子树的加分 右子树的加分根的分数右子树的加分根的分数 若某个树缺少左子树或右子树，规定缺少的子若某个树缺少左子树或右子树，规定缺少的子树加分为树加分为1。构造符合条件的二叉树构造符合条件的二叉树 该树加分最大该树加分最大 输出其前序遍历序列输出其前序遍历序列 样例样例 中序遍历为中序遍历为1,2,3,4,5的二叉树有很多，下图的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为是其中的三棵，其中第三棵加分最大，为145.分析 性质：中序遍历是按性质：中序遍历是按“左左-根根-右右”方式进行遍历二叉树，方式进行遍历二叉树，因此二叉树左孩子遍历

27、序列一定在根结点的左边，右孩子因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！遍历序列一定在根结点的右边！因此，假设二叉树的根结点为因此，假设二叉树的根结点为k，那么中序遍历为，那么中序遍历为1,2,n的遍历序列，左孩子序列为的遍历序列，左孩子序列为1,2,k-1，右孩子序列为，右孩子序列为k+1,k+2,n，如下图，如下图动态规划 设设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 时间

28、复杂度时间复杂度 O(n3)要构造这个树，只需记录每次的决策值，令要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为表示中序遍历为i,i+1,j的二叉树的取最优决策时的二叉树的取最优决策时的根结点为的根结点为k 最后前序遍历这个树即可。最后前序遍历这个树即可。思考题：选课思考题：选课 大学里实行学分。每门课程都有一定的学分，学生只要选大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。学分是他选修的各门课的学分的总和。每个学生都要选择规定数量的

29、课程。其中有些课程可以直每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，的一些课程的基础上才能选修。例如，数据结构数据结构必须必须在选修了在选修了高级语言程序设计高级语言程序设计之后才能选修。我们称之后才能选修。我们称高级语言程序设计高级语言程序设计是是数据结构数据结构的先修课。每门课的的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为课。为便于表述

30、每门课都有一个课号，课号依次为1 1，2 2，3 3，。每个学生可选课程的总数是给定的。现在请你找出一种选每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。先的原则。假定课程之间不存在时间上的冲突。输入输入 输入文件的第一行包括两个正整数输入文件的第一行包括两个正整数M M、N N（中间用一个空（中间用一个空格隔开）其中格隔开）其中M M表示待选课程总数（表示待选课程总数（1M1000)1M1000)，N N表示表示学生可以选的课程总数（学生可以选的课程

31、总数（1NM)1NM)。以下以下M M行每行代表一门课，课号依次为行每行代表一门课，课号依次为1 1，2 2M M。每行。每行有两个数（用一个空格隔开），第一个数为这门课的先修有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为课的课号（若不存在先修课则该项为0 0），第二个数为这），第二个数为这门课的学分。学分是不超过门课的学分。学分是不超过1010的正整数。的正整数。输出输出 输出文件第一行只有一个数，即实际所选课程的学分总输出文件第一行只有一个数，即实际所选课程的学分总数。以下数。以下N N行每行有一个数，表示学生所选课程的课号。行每行有一个数，表示学生所选

32、课程的课号。问题问题7：聚会的快乐：聚会的快乐 你要组织一个由你公司的人参加的聚会。你希望聚会非常你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定请某个人和他的上司，因为这可能带来争吵。给定N个人个人(姓名，他幽默的系数，以及他上司的名字姓名，他幽默的系数，以及他上司的名字)，编程找到能，编程找到能使幽默系数和最大的若干个人。使幽默系数和最大的若干个人。【输入输入】第一行一个整数第一行一个整数N(N100)。接下来有。接下来有N行，每一行描述一行，每

33、一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，幽默系数是在的字符串，幽默系数是在0到到100之间的整数。之间的整数。【输出输出】所邀请的人最大的幽默系数和。所邀请的人最大的幽默系数和。样例【样例样例】party.in party.out58BART 1 HOMERHOMER 2 MONTGOMERYMONTGOMERY 1 NOBODYLISA 3 HOMERSMITHERS 4 MONTGOMERY分析 首先，很显然公司的人员关系构成了一棵树。设首先，很显然公司的人员关系构成了一棵树。设fa为为a参加会议的情况下，以他

34、为根的子树取得的最大参加会议的情况下，以他为根的子树取得的最大幽默值；幽默值；ga为为a不参加会议的情况下，以他为根的不参加会议的情况下，以他为根的子树取得的最大幽默值。那么，状态转移方程就是：子树取得的最大幽默值。那么，状态转移方程就是：fa=gb1+gb2+gbk+1ga=max(fb1,gb1)+max(fb2,gb2)+max(fbk,gbk)其中其中b1,b2,bk为为a的子结点。的子结点。最后的答案就是最后的答案就是max(froot,groot)，root是树是树思考题：警卫安排思考题：警卫安排 一个有一个有N个区域的树结构上需要安排若干个警卫；个区域的树结构上需要安排若干个警卫；每个区域安排警卫所需要的费用是不同的；每个区域安排警卫所需要的费用是不同的；每个区域的警卫都可以望见其相邻的区域，只要一每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；域就是安全的；任务：在确保所有区域都是安全的情况下，找到安任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；排警卫的最小费用；0n=720；联系方式 长沙市雅礼中学 朱全民 410007