《树形动态规划》PPT课件

《《树形动态规划》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树型动态规划JSOI2010冬令营引言树是一种特殊的图，可以描述比较复杂的关系，而大多数动归都是在一维二维这种规则的背景下的，再加上树递归定义的性质，可以说是一种非常合适的动归框架，树型动态规划就成为动规中重要的一类题型。因为树可以描述比较复杂的关系，这对选手分析问题的能力有较高的要求，在寻找最优子结构、组织状态时往往需要创造性思维，而且树型动态规划对数学要求不高，一般不涉及单调性优化，所以竞赛中往往将它作为侧重考察选手分析思考能力的题出现。例一、问题描述给定一棵树，树的每个节点有一个权值，要求从中选出一些不相邻的点，使选出的节点权值和最大。例一、确定状

2、态对于大多数树型动态规划问题，都是用一棵子树的根节点编号来作为代表这棵子树的第一维状态，然后再根据需要加维。对于本题：用f[i][0]表示不选i时，以i为根子树的最大权值；用f[i][1]表示选择i时，以i为根子树的最大值。例一、状态转移f[i][0]=sum(max(f[j][0],f[j][1]))f[i][1]=sum(f[j][0])例一、状态转移因为树的特殊结构，任何两个点只有唯一通路，所以很容易满足无后效性。假如本题给定的是图而不是树，那么显然就无法用动归解决了。例一、两种实现方式记忆划搜索：易于实现，但可能会爆栈拓扑排序＋动归：实现起来比较

3、麻烦例一、两种实现方式实现方式的选择因题而异，对于本题，首先要保证程序不会出错。但一般来说，在保证正确的前提下，记忆划搜索更加易于实现，且在对于复杂的题目，记忆划搜索更加直观，便于思考。例二、问题描述在一棵节点数不超过200000的树中，每条边都有一个长度值，现要求在树中选择3个点X、Y、Z，满足X到Y的距离不大于X到Z的距离，且X到Y的距离与Y到Z的距离之和最大，求这个最大值。例二、问题分析三种情况例二、问题分析

4、XY

5、+

6、YZ

7、

8、XY

9、+

10、YX

11、+

12、XZ

13、例二、问题分析例二、问题分析现在只要考虑这一种情况要满足

14、Xa

15、＋

16、aY

17、≦

18、Xa

19、+

20、aZ

21、

22、

23、Xa

24、＋2

25、aY

26、＋

27、aZ

28、最大例二、问题分析现在我们考虑分叉点a很明显，要使目标值最大，XYZ必是离a最远的三点，且在以a为根的三棵不同子树中。Y就是三点中离a第二远的点。显然，三个点要么位于以a为根的子树中，要么位于以a为根的子树外。例二、问题分析求在子树中的三个最远点，方法很简单。在儿子已经算好的情况下，父节点只要保留其中最远点最远的三个儿子的最远点即可。子树外的最远点如何求？例二、问题分析把这棵树再遍历一遍，进行一次BFS，深度小的先访问，深度大的后访问，就保证了访问到某一个节点的时候，其父亲节点已经被访问过了。此次遍历时，对于点a，检查其父亲节

29、点，只需求出到其父亲节点的最远的，且不在以a为根的子树中的那点即可。例三、问题描述有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。这棵树共有N（1<=N<=100）个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量P，求出最多能留住多少苹果。例三、问题分析这题的权值在边上，这在思考时有些别扭，其实只要把边的权值转移到儿子节点上，问题性质不变。这样状态就应该容易想到了，f[i][j]表示以i节点为根的子树保留j个节点所得的最大值。因为根

30、节点没有权值，所以我们要保留p+1个点。例三、状态转移f[i][j]＝max｛f[i_left][k]+f[i_right][j-1-k]｝(0<=k<=j-1)边界f[i][0]＝0；f[i][1]=value[i]最后f[1][p+1]就是答案例四、问题描述学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。在选修课程中，有些课程可以直接选修，有些课程有一门直接的先修课。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上

31、的冲突。例四、问题分析由于每门课至多只有一门直接先修课，我们把没有先修课的课强制规定一门空的先修课，这样所有课就构成了一棵树。现在就是要从中选出m＋1门课，被选择的课必须满足其所有祖先都被选择。例四、问题分析这样看来这题和上题差不多：从根开始，把m＋1个机会分配下去。状态也很容易想到，f[i][k]表示以i为根的子树中选k门课的最大学分。但是这题的树不是二叉的，这就不能用上题的方法分配附加维了。例四、问题分析假设某个节点的所有孩子的状态值都已经计算出来了，现在要据此计算出该节点所有状态值。对于某一孩子i，可以视为一个没有固定的费用和价值，它的价值随着分配

32、给它的费用而变化的物品。这就是一类经典的背包问题了，每次利用计算好的儿子求父亲的