动态规划专题：树型动态规划

1、动态规划专题（六）：树型动态规划（重庆巴蜀中学黄新军）信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收益） 完成给定的操作。有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变成了棘 手的问题。这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解， 因此要用动态规划解决。和一般动态规划问题一样，这类问题的解决要考虑如下三步：1、确立状态：几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据具体 问题考虑是否要加维，加几维，如何加维。2、状态转移：状态转移的变化比较多，要根据具体问题具体分析，这也是本文例题分 析的重点。3、算法实现：由于树的

2、结构，使用记忆化搜索比较容易实现。由于模型建立在树上，即为树型动态规划。【例题1】二叉苹果树【问题描述】有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点），这 棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N，树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝 的树：现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数 量，求出最多能留住多少苹果。【文件输入】第1行2个数，N和Q（1v=Qv=N,1vNv=100）。N表示树的结点数，Q表示要保留的树 枝数量。接下来N-1行描述树枝的信息。每行3个

3、整数，前两个是它连接的结点的编号。 第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。【文件输出】输出文件仅一个数，表示最多能留住的苹果的数量。3【样例输入】4 103 205 20【样例输出】21【思路点拨】由题意可知，需要保留的树枝数量为Q条，即保留结点t=Q+1个。树根必须保留，可 以分三种情况讨论保留苹果的最大数。树根的左子树为空，全部保留右子树，右子树中保留t-1个结点；树根的右子树为空，全部保留左子树，左子树中保留t-1个结点；树根的两棵子树都为非空，设左子树保留k个结点，则右子树保留t-k-1个结点。要得到保留树根时的苹果最大数，只需要求上述三个方案中的最大值。

4、设树根为V，左 儿子为chv,1,右儿子为chv，2，对于方案，要取得该方案的最大值，需要取得以chv， 2为根，保留t-1个结点的最大值。这时同样具有上述三种方案。其他情况同理；由此 可以看出，该问题具有明显的最优子结构性质，每个问题都与左右儿子结点有关系，但不与 孙子结点发生关系，具备无后效性；且计算方案时，搜索子结构时具备重叠性，所以可以用 动态规划来解决。阶段和状态：fv，t：表示以v为根的树上保留t个节点的最大权值和。设chv，1,chv， 2分别存v节点的左右孩子。状态转移方程：fv,t=maxfchv,1i+fchv,2t-i-1+numv(0=i=t-1)初始化：fv,t=0,

5、(t=0)；fv,t=numv； (chv,1=0 且 chv,2=0)Answer=f1,t；【例题2】加分二叉树(NOIP2003)【问题描述】设一棵n个结点的二叉树tree的中序遍历为(1,2,3,.,n)，其中数字1,2,3,.,n为结点编 号。每个结点都有一个分数(均为正整数)，记第i个结点的分数为di，tree及它的每个子 树都有一个加分，任一棵子树subtree (也包含tree本身)的加分计算方法如下：subtree的左子树的加分xsubtree的右子树的加分+subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶结点本身的分数。不考虑它的空 子树。试求一棵符

6、合中序遍历为(1,2,3,.,n)且加分最高的二叉树tree。要求输出；tree的最高加分tree的前序遍历【输入格式】第1行：一个整数n (n30)，为结点个数。第2行：n个用空格隔开的整数，为每个结点的分数(分数100)。【输出格式】第1行：一个整数，为最高加分(结果不会超过4,000,000,000)。第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】55 7 1 2 10【输出样例】145【思路点拨】本题已经说明了问题的模型是一棵树，而且是一棵中序遍历为1,2,3,.,n的二叉树。而 对于一棵中序遍历为1,2,3,.,n的二叉树有很多种形式，对于样例，下图就列出了 3种形式，

7、 而按题意，第三种形式得到的得分最大。5(lA)2(5*1+7)*10+2=122(1*10+2)*5+7=67(5+7)*(10+2)+1=145性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一 定在根结点的左边，右孩子遍历序列一定在根结点的右边!因此，假设二叉树的根结点为k，那么中序遍历为1,2,.,n的遍历序列，左孩子序列为1,2,.,k-1，右孩子序列为k+1,k+2,.,n，如下图1,k-1kk+1.nII I左孩子根右孩子夕侦孩子k+1.,n左孩子我们思考的方式变为，要使得整棵树最优，必须左孩子和右孩子都最优，因此设fij 表示以结点i,i+1,i+2

8、.,j组成的二叉树所得的最大加分；设根为k，则枚举根结点dk表示 k结点的最大分值；故有：fi,j=maxfi,k-1*fk+1,j +dk;( 1=i=k=j=n)初始条件：fi,i=dkAnswer=f1,n时间复杂度：O(n3)题目还要求输出最大加分树的前序遍历序列，因此要构造这个树，我们只需记录每次的 决策值，令pi,j=k，表示中序遍历为i,i+1,.,j的二叉树的取最优决策时的根结点为k，最 后前序遍历这个树即可。【例题3】选课(CTSC1997)【问题描述】大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获 得相应的学分。学生最后的学分是他选修的各门课的

9、学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的 基础知识，必须在选了其他的一些课程的基础上才能选修。例如，数据结构必须在选修 了高级语言程序设计之后才能选修。我们称高级语言程序设计是数据结构的先 修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每 门课都有一个课号，课号依次为1,2,3,.。下面举例说明：课号先修课号学分学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个 学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且 必须满足先修课优先的原则。假定课程之间不存在时

10、间上的冲突。【文件输入】输入文件的第一行包括两个正整数M，N(中间用一个空格隔开)，其中M表示待选课程 总数(1=M=1000)，N表示学生可以选的课程总数(1=Nnm;for(i=1;ikv;ai.value=v;if(sonk=0)ak.left=i;else asonk.right=i;sonk=i;(2)树上的动态规划创建。以结点i为阶段，以选的课程数j为状态，以到达叶子结 点为边界，以每个结点能取得的最高得分为决策，在整棵树上的决策构成一个决策序列。用 fij表示结点i为根的子树中取j门课程的最高得分，对树型结构分2种情况进行动态规划 设计。由于是普通有序树或森林转换成的二叉树，所以

11、需要对右子树进行特殊处理。当只有 右子树时，此时i结点不能选，只能选择i结点的右子树，即选择课程数为j。所以此时的 状态转移方程为：fij=fi.r,j。由于要选择左子树时，树根必须选择，所以可以把只有左子树和左右子树都有两种合 并起来进行考虑，得到动态规划方程为：fij=maxfi.lk+fi.rj-k-1+ai(0=kx且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可 以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没 有重复数字出现的最多变换步数。【文件输入】输入一个正整数n【文件输出】输出不断进行数字变换且没有重复数字出现的最多变换步数。【样

12、例输入】7【样例输出】3【样例说明】一种方案为：4317。【数据范围】nd1i，则 d2i=d1i; d1i=d1j+1;否则，若 d1j+1d2i，则 d2i=d1j+1;最后扫描所有的结点，找最大的d1i+d2i的值。【例题5】战略游戏【问题描述】Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现 在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的 士兵，使得这些士兵能瞭望到所有的路。注意：某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。【文件输入】

13、输入文件中数据表示一棵树，描述如下：第一行N，表示树中结点的数目。第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边 与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2, .，rk。对于一个n(0n=1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只 出现一次。【文件输出】输出文件仅包含一个数，为所求的最少的士兵数目。【样例输入】40 1 1 TOC o 1-5 h z HYPERLINK l bookmark140 o Current Document 2 2 30 HYPERLINK l bookmark109 o Curr

14、ent Document 0【样例输出】1【思路点拨】按照要求构建一张关系图，可见这是一棵树。对于这类最值问题，向来是用动态规划求解的。任何一个点的取舍可以看作一种决策，设fi,1表示i点放士兵时，以i为根的子树需要 的最少士兵数目；fi,0表示i点不放士兵时，以i为根的子树需要的最少士兵数目。当点i不放时，则它的所有儿子都必须放，即fi,0=fi,0+fj,1；其中j为i的儿子。当点i放时，则它的所有儿子放与不放无所谓，但应该取两种情况的最大值。即fi,1=fi,1+max(fj,1,fj,0)；其中 j 为 i 的儿子。初始条件：fi,0=0;fi,1=1【例题6】皇宫看守【问题描述】太平

15、王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望 见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安 排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。【文件输入】输入文件中数据表示一棵树，描述如下：第1行n，表示树中结点的数目。第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i(0i=n), 在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数，分别是

16、这个节点的m个儿 子的标号 r1,r2,.,rm。对于一个n(0n=1500)个结点的树，结点标号在1到n之间，且标号不重复。【文件输出】输出文件仅包含一个数，为所求的最少的经费。【样例输入】61 30 3 2 3 42 16 2 5 65*115 11 0【样例输出】25【分析样例】该图有6个区域如图1,安排情况如图2,红色点为安排了警卫。2号警卫可以观察1, 2, 5, 6； 3号警卫可以观察1, 3； 4号警卫可以观察1, 4； 费用：16+5+4=25【试题分析】本题已知模型是一棵树，因此我们试着用树形动态规划来解决。对于本题，每个安全结 点i,都有3种状态分别为：要么在父亲结点安排警

17、卫，即被父亲看到要么在儿子结点安排警卫，即被儿子看到要么安排警卫设f(i,0)表示i结点被父亲看时，以i为根的子树需要安排的最少士兵; f(i,1)表示i被它的儿子看时，以i为根的子树需要安排的最少士兵; f(i,2)表示在i安排警卫时，以i为根的子树需要安排的最少士兵；父亲结点当前结点i l儿子结点4现在只需针对这三种状态，设计出状态转移方程。对于f(i,0)，表示i被父亲看到，这时i没有安排警卫，i的儿子要么安排警卫，要 么被它的后代看到，所以有：f /,0=的 mnf g ,1, f i.k ,2k=1对于f(i,1),表示i被儿子看到，即i的某个儿子安排了警卫，其他儿子需要安排警 卫或者被它的后代看到，所以有：f i,1 = i 的云 3inf i.k ,1, f ik ,2 + dk=1其中 d = minf i.k ,2 - minf i.k ,1, f i.k ,2对于f(i,2),表示i安排了警卫，i的儿子可以安排警卫，也可以被i的儿子的儿子 看守，还可以被父亲看守，所以有：f i,2= 的尤ILinf i.k ,0, f i.k ,1