树形动态规划03

1、树形动态规划树形动态规划什么是树型动态规划什么是树型动态规划 l树上没有环，所以dfs时不会有重复；n个点的树只有n-1条边。l顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向:向前和向后，相应的线性的动态规划有二种方法既逆推与顺推，而树型动态规划是建立在树上的，所以也相应的有二个方向： （1）根叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。 （2）叶根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解

2、法。 什么是树型动态规划什么是树型动态规划l树形动态规划的题目需要先给出所有的边构造树，当然要使用尽量小的空间和时间，且一般将树转换成左儿子右兄弟的形式存储左儿子右兄弟的形式存储 （m叉树和森林转换为二叉树的方法），这是所有树形动态规划问题的基础。 l因为树的定义和建立是递归的，所以，树形动态规划很少去划分阶段，更多的用的是记忆化搜索。l图论的权值都在边上，而树的权值一般都在点上，这一点需要好好思考。加分二叉树加分二叉树l【问题描述】l 设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，

3、tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：l subtree的左子树的加分 subtree的右子树的加分subtree的根的分数l 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空l子树。l 试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出；l （1）tree的最高加分l （2）tree的前序遍历【输入格式】 第1行：一个整数n（n30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】 第1行：一个整数，为最高加分（结果不会超过4,000

4、,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】 5 5 7 1 2 10【输出样例】 145 3 1 2 4 5分析分析l性质：中序遍历是按性质：中序遍历是按“左左-根根-右右”方式进行遍历二叉树，因此二叉方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！根结点的右边！l因此，假设二叉树的根结点为因此，假设二叉树的根结点为k，那么中序遍历为，那么中序遍历为1,2,n的遍历的遍历序列，左孩子序列为序列，左孩子序列为1,2,k-1，右孩子序列为，右孩子序列为k

5、+1,k+2,n，如，如下图下图分析分析如果整棵树的权值最大，必然有左子树的权值最大，右子树的权值也最大，符合最优性原理。动态规划动态规划l设设f(i,j)中序遍历为中序遍历为i,i+1,j的二叉树的最大加分，则有：的二叉树的最大加分，则有： f(i,j)=maxfi,k-1*fk+1,j +dkl显然显然 f(i,i)=dil答案为答案为f(1,n)l1=i=k=j=nl时间复杂度时间复杂度 O(n3)l要构造这个树，只需记录每次的决策值，令要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为表示中序遍历为i,i+1,j的二叉树的取最优决策时的根的二叉树的取最优决策时的根结

6、点为结点为kl最后前序遍历这个树即可。最后前序遍历这个树即可。总结总结l输出因为要输出树的结构，所以，还要在动态规划的过程中，把每个区间的根给求出来。l 设 rootI,j 为第i个元素 到第j个元素的根。这样就可以确定树的结构了。此题是批着 树形 外观的 非树形动态规划题。而真正的树形动态规划是在树上做动态规划。 苹果二叉树苹果二叉树 （apple） 题目描述题目描述 有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。 现在这颗树枝条太多

7、了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。输入格式输入格式第1行2个数，N和Q(1=Q= N,1N=0 thenl beginl chv,1:=i; l numi:=mapv,i; l mapv,i:=-1;mapi,v:=-1; l maketree(i); l break; l end; l for i:=1 to n do l if mapv,i=0 then l begin l chv,2:=i; l numi:=mapv,i; l mapv,i:=-1;mapi,v:=-1; l maketree(i); l break; l end; l

8、end;如何求最优解如何求最优解l贪心是不可以的。l类似于资源分配，根节点的最优值肯定与左子树和右子树的最优值有关系。l局部最优可以推出全局最优。l并且根据树的特性，一旦某个结点为根的最优值确定，肯定不再受到其父节点的影响。符合无后效性。l可以用动态规划来做。动态规划设定动态规划设定l根据前边动态规划的经验，状态函数是第一要务，那么状态应该怎么表示呢？l仿照线性的，我们设 chv,1 和 chv,2分别表示 v节点的左孩子和右孩子。lfi,j表示 以第i个节点为根的子树保留j个节点的最大权和。l那么转移方程就是lFi,j=max(fchi,1,k)+fchi,2,j-k-1)l (0=k=j-

9、1)(想一下，为什么右子树是 j-k-1)如何实现如何实现l树形结构本身就是递归结构。所以，我们用的更多的递归的形式来构造树。l而在状态转移的时候，我们一般都是叶子节点出发，根节点为最终结果。这样，如果用记忆化搜索的方式，动态规划的过程和构造树的方向基本一致，有时候还可以合二为一。l反思:树形是严格的分层的，每个节点都有严格的父节点，并且没有环，所以，会产生重复么？先写出先写出dfs框架框架Procedure dfs(v); var i:longint;Begin for i:=1 to n do if fatheri=v then begin dfs(i); dpv fun(dpi) end

10、;End;代码分析代码分析l思考代码的框架?l参数：和状态对应。 V，k：v代表树的节点编号,k代表以v为根的子树保留多少个节点。l边界：到叶子节点，直接返回值。 如果k是0，返回0.l搜索范围：递归本身就包含左右子树，穷举的子树里k的值，状态转移用。l代码如下，仔细思考。l边界为什么没有先判断是否搜索过？主要过程主要过程l procedure dfs(v,k:longint); l var l i:longint; l begin l if (k=0) then dpv,k:=0 l else if (chv,1=0)and(chv,2=0) then dpv,k:=numv l else

11、begin l dpv,k:=0; l for i:=0 to k-1 do l begin l if dpchv,1,i=0 then dfs(chv,1,i); l if dpchv,2,k-i-1=0 then dfs(chv,2,k-i-1); l dpv,k:=max(dpv,k,dpchv,1,i+dpchv,2,k-i-1+numv); l end; l end; l end;主程序主程序l begin l readln(n,q); l for i:=1 to n do for j:=1 to n do mapi,j:=-1; l for i:=1 to n-1 do l beg

12、in l readln(a,b,c); l mapa,b:=c;mapb,a:=c; l end; l maketree(1); l dfs(1,q+1); l writeln(dp1,q+1); l end. l本道题就是一道最基本的树形动态规划题。一般树形动态规划题目分为两个步骤l(1) maketree，l(2) treedpl在树的存储结构上，我们一般选的都是二叉树，因为二叉树可以用静态数组来存储，并且状态转移也很好写。l如果是多叉怎么办？最大利润最大利润l【题目描述】【题目描述】l政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火政府邀请了你在火车站开饭店，但不允许同时在两个相

13、连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。个和它相连接的火车站。l告诉你每个火车站的利润，问你可以获得的最大利润为多少。告诉你每个火车站的利润，问你可以获得的最大利润为多少。l例如下图是火车站网络：例如下图是火车站网络：l最佳投资方案是在最佳投资方案是在1，2，5，6这这4个火车站开饭店可以获得利润个火车站开饭店可以获得利润为为90l【输入格式】【输入格式】l第一行输入整数第一行输入整数N(=100000)，表示有，表示有N个火车站，分别用个火车站，分别用1，2。，。，N来编号。接下来来编号

14、。接下来N行，每行一个整数表示每个站点的利润，接下来行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。行描述火车站网络，每行两个整数，表示相连接的两个站点。l【输出格式】【输出格式】l输出一个整数表示可以获得的最大利润。输出一个整数表示可以获得的最大利润。l【样例输入】【样例输入】l6 10l 20l25l40l30l30l4 5l1 3l3 4l2 3l6 4 l【样例输出】【样例输出】l90分析l因为因为N个点个点,N-1条边，任意两个火车站有且只有一条路径，所以是条边，任意两个火车站有且只有一条路径，所以是一棵树一棵树.但是不是二叉树。

15、但是不是二叉树。l没有根的话，就随意指定一个点为根。没有根的话，就随意指定一个点为根。l我们用我们用FX表示在以表示在以X为根的树中开饭店，为根的树中开饭店，X一定要开，所能获得一定要开，所能获得的最大利润，的最大利润，GX 表示在以表示在以X为根的树中开饭店，为根的树中开饭店，X一定不开，所一定不开，所能获得的最大利润，我们知道能获得的最大利润，我们知道X开，则它的儿子们开，则它的儿子们Y1,Yk一定不一定不能开，能开，X不开，它的儿子们可开可不开，于是得到以下状态转移方不开，它的儿子们可开可不开，于是得到以下状态转移方程：程：l FX= (Yi是是X的儿子的儿子)l G(X)= l实现时用

16、实现时用DFS去实现，每个点只需求一次，所以时间复杂度为去实现，每个点只需求一次，所以时间复杂度为O(N)KiYiG1)(KiYiGYiF1)(),(max(选课选课（如果看不清，看下一页）（如果看不清，看下一页）l在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？l输入：l第一行有两个整数N,M用空格隔开。

17、(1=N=300,1=M=200)l接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1=ki=N, 1=si=20）。l输出：l只有一行，选M门课程的最大得分。l输入样例： l7 4 l2 2 l0 1 l0 4 l2 1 l7 1 l7 6 l2 2 l输出样例： l13 分析分析l每门课程最多只有每门课程最多只有1门直接先修课，如果我们把课程门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。看成结点，也就是说每个结点最多只一个前驱结点。l如果把前驱结点看成父结点，换句话说，每个结点

18、只如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。要么是一棵树，要么是一个森林。l这样，问题就转化为在一个这样，问题就转化为在一个M个结点的森林中选取个结点的森林中选取N个结点，使得所选结点的权值之和最大。同时满足每个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。次选取时，若选儿子结点，必选根结点的条件。样例分析样例分析l如图如图1，为两棵树，我们可以虚拟一个结点，将这些，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会

19、为了树连接起来，那么森林就转会为了1棵树，选取结点棵树，选取结点时，从每个儿子出发进行选取。显然选时，从每个儿子出发进行选取。显然选M=4时，选时，选3，2，7，6几门课程最优。几门课程最优。动态规划动态规划l如果我们单纯从树的角度考虑动态规划，设以如果我们单纯从树的角度考虑动态规划，设以i为根结点的树选为根结点的树选j门门课程所得到的最大学分为课程所得到的最大学分为f(i,j), 设虚拟的树根编号为设虚拟的树根编号为0，学分设为，学分设为0，那么，那么，ans=f(0,n+1)如果树根选择如果树根选择1门功课，剩下门功课，剩下j-1门功课变成了给他所有儿子如门功课变成了给他所有儿子如何分配的

20、资源的问题，这显然是背包问题。何分配的资源的问题，这显然是背包问题。设前设前k个儿子选修了个儿子选修了x门课程的最优值为门课程的最优值为g(k,x)，则有，则有l其中其中: 0=xgt1,j then begin gt1,j:=gt0,j-k+ft1,k; fat1,j:=k; / fai,j 表示表示now为根的子树到第为根的子树到第t1门课时选取门课时选取j门课的最优值时，第门课的最优值时，第t1门选了门选了k门。门。 end; end; for i:=m downto 1 do fnow,i:=gnenow,tnow,i-1+vnow; end;进一步分析进一步分析l上述状态方程，需要枚

21、举每个结点的上述状态方程，需要枚举每个结点的x个儿子，而个儿子，而且对每个儿子的选课选择，需要再进行递归处理。且对每个儿子的选课选择，需要再进行递归处理。l当然这样可以解决问题，那么我们还有没有其他方当然这样可以解决问题，那么我们还有没有其他方法呢？法呢？转化为二叉树转化为二叉树如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。该问题转化为二叉树求解。图图2就是对图就是对图1采用孩子兄弟表示法所得到的二叉树

22、采用孩子兄弟表示法所得到的二叉树动态规划动态规划l仔细理解左右孩子的意义（如右图）：仔细理解左右孩子的意义（如右图）：左孩子：原根结点的孩子左孩子：原根结点的孩子右孩子：原根结点的兄弟右孩子：原根结点的兄弟l也就是说，左孩子分配选课资源时，也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。根结点必须要选修，而与右孩子无关。l因此，我们设因此，我们设f(i,j)表示以表示以i为根结点的二叉树分配为根结点的二叉树分配j门课程的所获得门课程的所获得的最大学分，则有，的最大学分，则有，l0=kj n m; scoren+1 = 0; brothern+1 = 0; / 输入数据并转化为左儿子右兄弟表示法输入数据并转化为左儿子右兄弟表示法 for (int i=1; i a b