|
动态规划详解 第三章
这一章，我们来学习树形动态规划。
动态规划一般来说分为四大类：线性动态规划，区间动态规划，树形动态规划和特殊种类动态规划。 因为线性模型和区间类模型紧密相关，所以一般我们将这两种类型放在一起学习。 树形动态规划和以上两种不同，它是在一个树结构中进行的，因此具有一般性， 而特殊种类动态规划则包含比较广，譬如状态压缩， 博弈以及其他各种问题都可以归纳到这个部分，因为问题比较分散， 所以这个部分就请大家自己学习，可以参考历年国家集训队论文， 对这个部分的讨论十分透彻和深入。 下面就让我们来学习树形动态规划。 首先看一道例题： 例：给定一棵树T，树中每个顶点u都有一个权w(u)，权可以是负数。 现在要找到树T的一个个连通子图使该子图的权之和最大。 分析一下这道题，我们发现，对于节点A，如果考虑以他为根的一棵子树， 那么它的最优值和他的父节点无关，所以转移方程为： F[I]=sigma{F[son],当F[son]>0时}+w(u) 最终的答案为F[X]中的最大值。 因为是在一棵树当中进行动态规划，所以不妨用递归的形式来编写。 通过上面的例子，相信大家对树形动态规划有了一个初步的认识， 其实树形动态规划属于动态规划中一个较难的问题，因为约束条件往往比较多， 所以状态的转移并不容易，下面看一个较难的例子： 在一棵树中，每条边都有一个长度值，现要求在树中选择3个点X、Y、Z， 满足X到Y的距离不大于X到Z的距离，且X到Y的距离与Y到Z的距离之和最大，求这个最大值。 其中顶点个数N<=2000000 因为数据规模很大，所以考虑O(N)或者O(NlogN)的算法。 分析问题，我们发现因为在一棵树中，所以x,y,z的路径中必定有一个交点k， 距离S=xk+2*ky+kz，我们发现，若要S达到最大值， 那么只需要ky,xk,kz为以k为根的树中三个不在同一子树中的最大的三个距离就可以了， 但是这样的时间复杂度依然为O(n^2)，继续分析发现， 实际上第一次求出以某个节点为根的距离后， 只需要以这个点为根再dfs遍历一遍就可以求出其他的节点距离，所以总的时间复杂度为O(N)。 再次回味一下这道题的解题思路：我们首先从数据规模确定了算法的复杂度， 并通过对模型的初步分析得到了一些性质，然后通过这些性质得到了新的解题思路， 这其实是解树形动态规划乃至其他问题的一个一般性的思路。 通过对树模型的特殊性分析，可以大大的降低时间复杂度。 最后让我们来看一个很具有发散性的题目： 奶牛成群、土地众多的FJ有一个地形狭长的农场，农场被分成了n块土地，n不超过1000。 这些土地位于一条直线上，并从左到右编号为1至n。每块土地的面积都相同， 但是高度不一定相同。每块土地都拥有一个海拔高度值，这个值不超过1000000。 如果一段相同高度土地的两边都比它低或者是农场的边界，那么这段土地将被称之为“山顶”。 FJ希望通过搬走泥土来降低某些土地的海拔高度，使“山顶”的数目不超过k，其中1≤k≤25。 在这一前提下，FJ希望搬运的泥土体积最小，也就是所有的土地减少的高度和最小。 初看上去这道题似乎和树形动态规划没有什么关系，根本没有树结构的样子， 分析一下我们发现，所谓的山峰，就是每个层中不连接的部分，所以从层的角度思考， 显然，每个层之与他的上层和他的下层的有关，与层的长度无关，所以不访化层为点， 以地面为基础节点，每一层不连接“块”为一个节点，用边连接不同层的相邻的点， 我们惊讶的发现，这些点构成了一棵树！ 进一步分析，发现每次“削平”一个山顶，在树中就是删除一个最叶子节点， 而消除的高度则可以看作是节点的权值，这样，问题就转化到了在树中删除一些节点， 使最终的节点数目不超过k+1，并且剩余权值最大的问题，复杂度为o(nk^2)。 多么巧妙的转化！一道看似复杂的问题就这样解决了，以无限为有限,以无法为有法，这或许就是算法的魅力。 <<<<<<<<<<<<<<<<<<<<<<<<<To be continue>>>>>>>>>>>>>>>>> |
|
|
