动态规划专题(六)：树型动态规划

动态规划专题（六）：树型动态规划

信息学竞赛中通常会浮现这样的问题：给一棵树，要求以至少的代价（或者取得最大收益）

完成给定的操作。有不少问题都是在树和最优性的基础上进行了扩充和加强，从而变成为了

棘手的问题。这种问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优

解，因此要用动态规划解决。

和普通动态规划问题一样，这种问题的解决要考虑如下三步：

1、确立状态：几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据具体

问题考虑是否要加维，加几维，如何加维。

2、状态转移：状态转移的变化比较多，要根据具体问题具体分析，这也是本文例题分

析的重点。

3、算法实现：由于树的结构，使用记忆化搜索|比较容易实现。

由于模型建立在树上，即为树型动态规划。

【例题1】二叉苹果树

【问题描述】

有一棵苹果树.如果树枝有分叉.一定是分2叉（就是说没有惟独1个儿子的结点）.这

棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝

的树：

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有平果。给定需要保留的树枝数

量，求出最多能留住多少苹果。

【文件输入】

第1行2个数，N和Q（1<=Q<=N,1<N<=100）oN表示树的结点数，Q表示要保留的树

枝数量。接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。

第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。

【文件输出】

输出文件仅一个数，表示最多能留住的苹果的数量。

【样例输入】

25

52

131\/

1410

2320

35201

【样例输出】21

【思路点拨】

由题意可知，需要保留的树枝数量为Q条，即保留结点t=Q+1个。树根必须保留，可

以分三种情况讨论保留苹果的最大数。

①树根的左子树为空，全部保留右子树，右子树中保留个结点；

②树根的右子树为空，全部保留左子树，左子树中保留个结点：

③树根的两棵子树都为非空，设左子树保留个结点，则右子树保留个结点。

要得到保留树根时的苹果最大数，只需要求上述三个方案中的最大值。设树根为，左

儿子为右儿子为，，对于①方案，要取得该方案的最大值，需要取得以，

为根，保留个结点的最大值。这时同样具有上述三种方案。其他②③情况同理；由此

可以看出，该问题具有明显的最优子结构性质，每一个问题都与摆布儿子结点有关系，但不

与孙子结点发生关系，具备无后效性；且计算方案时，搜索子结构时具备重叠性，所以可

以用动态规划来解决。

阶段和状态：f[v,t]：表示以V为根的树上保留t个节点的最大权值和。设ch[v,1],ch[v,

2]分别存v节点的摆布孩子。

状态转移方程：

f[v,t]=max{f[ch[v,1]][i]-»-f[ch[v,2]][t-i-1]+num[v]}(0<=i<=t-1)

初始化：f[v,t]=O,(t=O)；

f[v,t]=num[v]；(ch[v,1]=0Kch[v,2]=0)

Answer=f[1,t]：

[例题2]加分二叉树(NOIP2003)

【问题描述】

设一棵n个结点的二叉极tree的中序遍历为(1,2,3,...,n),其中数字1,2,3,…,n为结点编

号。每一个结点都有一个分数(均为正整数)，记第i个结点的分数为di,tree及它的每一

个子树都有--个加分，任•棵了•树subtree(也包含tree本身]的加分计算方法如下：

subtree的左子树的加分subtree的右子树的加分+subtree的根的分数

若某个子树为空，规定其加分为1,叶子的加分就是叶结点本身的分数。不考虑它的空

子树。

试求一棵符合中序遍历为(l,2,3,...,n)且加分最高的二叉树tree。要求输出；

⑴tree的最高加分

(2)tree的前序遍历

【输入格式】

第1行：一个整数n(n<30),为结点个数。

第2行：n个用空格隔开的整数，为每一个结点的分数(分数<100)。

【输出格式】

第1行：一个整数,为最高加分(结果不会超过4,000,000,000)o

第2行：n个用空格隔开的整数，为该树的前序遍历。

【输入样例】

5

571210

【输出样例】

145

31245

【思路点拨】

本题已经说明了问题的模型是一棵树，而且是一棵中序遍历为1,2,3，…,n的二叉树。而

对于一棵中序遍历为123,…,n的二叉树有不少种形式,对于样例，下图就列出了3种形式,

而按题意，第三种形式得到的得分最大。

(5*1+7)*10+2=122(1*10+2)*5+7=67(5+7)*(10*2)*1»145

性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一

定在根结点的左边，右孩了•遍历序列一定在根结点的右边!

因此，假设二叉树的根结点为k,那末中序遍历为12…,n的遍历序列，左孩子序列为

右孩子序列为k+l,k+2,...,n,如下图：

kk+1..n

左孩子根右孩子

我们思量的方式变为,要使得整棵树最优，必须左孩子和右孩子都最优，因此设f[i][j]

表示以结点i,i+l,i+2...J组成的二叉树所得的最大加分；设根为k,则枚举根结点。d[k]表示

k结点的最大分值：故有：

f(i,j]=max{f[i,k-1]*f[k+1,j]+d[k]};d<=i<=k<=j<=n)

初始条件：f[i,i]=d[k]

Answer=f[1,n]

时间且杂度；O(n3)

题目还要求输出敢大加分树的前序遍历序列，因此要构造这个树，我们只需记录每次的

决策值，令p[i,jl=k,表示中序遍历为i,i+l,…,j的二叉树的取最优决策时的根结点为k,最

后前序遍历这个树即可。

[例题3]选课(CTSC1997)

【问题描述】

大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获

得相应的学分。学生最后的学分是他选修的各门课的学分的总和。

每一个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定

的基础知识，必须在选了其他的一些课程的基础上才干选修。例如，《数据结构》必须在

选修了《高级语言程序设计》之后才干选修。我们称《高级语言程序设计》是《数据结构

》的先修课。每门课的直接先修课最多惟独一门。两门课也可能存在相同的先修课。为便

于表述每

门课里有一个1号，课号挨?为123一下面举例说明：

课号|先修课号|学分

if(son[k]==0)a[k].left=i;

elsea[son[k]].right=i;

son[k]=i;

)

(2)树上的动态规划创建，以结点i为阶段，以选的课桂数j为状态，以到达叶子结

点为边界，以每一个结点能取得的最高得分为决策，在整棵树上的决策构成一个决策序列。

用表示结点i为根的子极中取j门课程的最高得分，对树型结构分2种情况进行动态

规划设计。

①由于是普通将序树或者森林转换成的二叉树，所以需要对右于树进行特殊处埋。当推

独右子树时，此时i结点不能选，只能选择i结点的右子树，即选择课程数为ja所以此

时的状态转移方程为:f[i][j]=f[i.r,j]o

②由于要选择左子树时，树根必须选择，所以可以把惟独左子树和摆布子树都有两种合

并起来进行考虑，得到动态规划方程为:f[i][j]=max{f[i.l][k]+f[i.r]0-k-1]+a[i]}(O<=k<=j-1)

最后取①②两种情况中的最大值，即可得到在i结点处取j门课程的最大值。

时间复杂度:Ogm)

【例题4]数字转换

【问题描述】

如果一个数x的约数和(不包括它本身，下同)比它本身小，那末x可以变成它的约数

和：如果对于某个y>x且y的约数和为x,那末x也可以变成y。例如，4可以变为3,1可

以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没

有重复数字浮现的最多变换步数。

【文件输入】

输入一个正整数n

【文件输出】

输出不断进行数字变换且没有重复数字浮现的最多变换步数。

【样例输入】

7

【样例输出】

3

【样例说明】

一种方案为：4T

【数据范围[n<=50OOOo

【思路点拨】

先预处理出每一个数的约数，然后很明显就是求树的最长链问题。

一棵有根树的最长链，可能浮现如下图的两种情况：

对于每一个结点我们都要记录两个值：d“i]表示以i为根的子树中，i到叶子节点的距

离最大值；d2[i]表示以i为杈的子树中，i到叶子节点的距离次大值；令j是i的儿子。则

①若d1[j]+1>d1[i],则d2[i]=d1[i];d1[i]=d10]+1；

②否则,若d1[j]+1>d2[i].WOd2[i]=d10]+1；

最后扫描所有的结点，找最大的的值。

【例题5]战略游戏

【问题描述】

Bob喜欢玩电脑游戏，特殊是战略游戏。但是他时常无法找到快速玩过游戏的办法。现

在他有个问题。

他要建立一个占城堡，城堡中的路形成一棵树。他要在这裸树的结点上放置至少数目的

士兵，使得这些士兵能瞭望到所有的路。

注意：某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。

请你编一程序，给定一树，帮Bob计算出他需要放置至少为士兵。

【文件输入】

输入文件中数据表示一棵树，描述如下：

第一行N,表示树中结点的数目。

第二行至第N+1行，每行描述每一个结点信息，挨次为：该结点标号i,k(后面有k条

边马结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1,r2,...»rko

对于一个n(0<n<=1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只

浮现一次。

【文件输出】

输出文件仅包含一个数，为所求的至少的士兵数目。

【样例输入】

4

011

1223

20

30

【样例输出】

1

【思路点拨】

按照要求构建一张关系图，可见这是一棵树。对于这种最值问题，向来是用动态规划求

解的。

任何一个点的取舍可以看做一种决策，设f[i刀表示i点放士兵时，以i为根的子树需要

的至少士兵数目：表示i点不放士兵时，以i为根的子树需要的至少士兵数目。

当点i不放时，则它的所有儿子都必须放,即仙0]=中1其中j为i的儿子。

当点i放时，则它的所有儿子放与不放无所谓，但应该取两种情况的最大值。即

f[i,1]=f[i,1]+max(f[j,1],f[j,0])；其中j为i的儿子。

初始条件：f[i,0]=0;f[i,1]=1

[例题6]皇宫看守

【问题描述】

太平王世子事件后，陆小风成为了皇上特聘的御前一品侍卫。

皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望

见。大内保卫森严，三步一岗，五步一哨，每一个宫殿都要有人全天候看守，在不同的宫殿

安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每一个宫殿都安置留守侍卫。

编程任务：匡助陆小凤布置侍卫，在看守全部宫殿的前提卜.，使得花费的经费至少。

【文件输入】

输入文件中数据表示一棵树，描述如下：

第1行n,表示树中结点的数目。

第2行至第n+1行，每行描述每一个宫殿结点信息，挨次为：该宫殿结点标号

i(O<i<=n),在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数，分别是这个节点

的m个儿子的标号r1,r2,...,nrio

对于一个n(0<n<=1500)个结点的树，结点标号在1到n之间，且标号不重复。

【文件输出】

输出文件仅包含•个数，为所求的至少的经费。

650

【样例输出】25

【分析样例】

%

该图有个区域如图，安排情况如图,红色点为安排了警卫。

号警卫可以观察，号警卫可以观察，：号警卫可以观察，

费用：

【试题分析】

本题已知模型是一棵树,因此我们试着用树形动态规划来解决。对于本题，每一个安全

结点i，都有3种状态分别为：

①要末在父亲结点安排警卫，即被父亲看到

②要末在儿子结点安排警卫，即被儿子看到

③要末安排警卫

设f(i,O)表示i结点被父亲看时，以i为根的子树需要安排的至少士兵:

表示i被它的儿子看时，以i为根的子树需要安排的至少士兵;

f(i,2)表示在i安排警卫时，以i为根的子树需要安排的至少士兵：

①