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

动态规划专题(六):树型动态规划(重庆巴蜀中学黄新军)信息学竞赛中通常会出现这样的问题:给一棵树,要求以最少的代价(或取得最大收益)完成给定的操作。有很多问题都是在树和最优性的基础上进行了扩充和加强,从而变成了棘手的问题。这类问题通常规模较大,枚举算法的效率无法胜任,贪心算法不能得到最优解,因此要用动态规划解决。和一般动态规划问题一样,这类问题的解决要考虑如下三步:1、确立状态:几乎所以的问题都要保存以某结点为根的子树的情况,但是要根据具体问题考虑是否要加维,加几维,如何加维。2、状态转移:状态转移的变化比较多,要根据具体问题具体分析,这也是本文例题分析的重点。3、算法实现:由于树的结构,使用记忆化搜索比较容易实现。由于模型建立在树上,即为树型动态规划。【例题1】二叉苹果树【问题描述】有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点),这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树:现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量,求出最多能留住多少苹果。【文件输入】第1行2个数,N和Q(1<=Q<=N,1<N<=100)。N表示树的结点数,Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数,前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。【文件输出】输出文件仅一个数,表示最多能留住的苹果的数量。【样例输入】52131141023203520【样例输出】21【思路点拨】由题意可知,需要保留的树枝数量为Q条,即保留结点t=Q+1个。树根必须保留,可以分三种情况讨论保留苹果的最大数。①树根的左子树为空,全部保留右子树,右子树中保留t-1个结点;②树根的右子树为空,全部保留左子树,左子树中保留t-1个结点;③树根的两棵子树都为非空,设左子树保留k个结点,则右子树保留t-k-1个结点。要得到保留树根时的苹果最大数,只需要求上述三个方案中的最大值。设树根为V,左儿子为ch[v,1],右儿子为ch[v,2],对于①方案,要取得该方案的最大值,需要取得以ch[v,2]为根,保留t-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]=0,(t=0);f[v,t]=num[v];(ch[v,1]=0且ch[v,2]=0)Answer=f[1,t];【例题2】加分二叉树(NOIP2003)【问题描述】设一棵n个结点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为结点编号。每个结点都有一个分数(均为正整数),记第i个结点的分数为di,tree及它的每个