`

【DP_树形DP专辑】【9月9最新更新】

 
阅读更多

转自:http://blog.csdn.net/woshi250hua/article/details/7644959

 

树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树、三叉树、静态搜索树、AVL树,线段树、SPLAY树,后缀树等等..

     枚举那么多种数据结构只是想说树方面的内容相当多,本专辑只针对在树上的动态规划,即树形DP.做树形DP一般步骤是先将树转换为有根树,然后在树上进行深搜操作,从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分,这个也没一般性的东西可讲,因为每道题目要求做的事都不尽相同。

     这个专辑暂时氛围3哥部分,分的可能不是很好,后面题目做多了理解更深了可能会更改,但那都是后话了。

 

一、常规树形DP

     1、 Hdu 1520 Anniversary party  每个节点有权值,子节点和父节点不能同时选,问最后能选的最大价值是多少?解题报告Here
      2、Hdu 2196 Computer  经典题,求树每个点到其他点的最远距离,转化为有根树,深搜两次,一次记录到叶子的最远距离,一次更新最终答案。解题报告Here
      3、Poj 1741 Tree(难)  经典题,求树上两点间距离小等于K的方案数,树上分治。解题报告Here
      4、Poj 2152 Fire(难)  罕见的O(n^2)的树形DP,在树上建消防站,要求每个节点离最近的消防站距离小于K,问最小花费。解题报告Here
      5、Poj 3162 Walking Race(难)  树形DP找最远距离+线段树查询最大最小值,然后再维护两个指针遍历整个序列。解题报告Here
      6、cf 218D. Choosing Capital for Treeland 把边方向转变成边权,正向为0,反向为1.经过转换,问题变成求某点为根到所有点的边权总和,求边权总和最小的那些点。

 

 

二、树形背包问题(在树上进行分组背包处理)

      1、Poj 1155 TELE  把每个节点的子节点看成一组背包,最大容量是这点的叶子子孙数量,选几个节点就是选择的容量,价值就是用户给的Money-中转费用。解题报告Here
      2、Hdu 1011 Starship Troopers 和上题相似,要选择父节点必先子节点,特判m为0的时候。
      3、Poj 1947 Rebuilding Roads 求最少删除几条边使得子树节点个数为p,具体的模型和上题很像。解题报告Here
      4、Hdu 1561 The more, The Better 在一棵树上选择若干个点获得的最大价值,选子节点必须先选父节点,求解情况和上两题相同。解题报告Here
      5、Hdu 4003 Find Metal Mineral (推荐,好题) 树形DP+选且只能选一个物品的分组背包,状态转移方程难想。解题报告here
      6、Poj 2486 Apple Tree 树形DP+分组背包,但是状态转移方程要分三步,较为难想。解题报告Here
      7、Poj 3345 Bribing FIPA  树形DP+分组背包,和前面几题相比没有特殊的地方,只是要注意输入。具体可见Here
      8、Hdu 4044 GeoDefense 树形DP+分组背包,要求从每个儿子结点获取最小的hp,然后找这些儿子的最大组合,不是特别好想。解题报告见Here
      9、Zoj 3627 Treasure Hunt II  树形DP +分组背包,浙大月赛的水题,很普通的树形背包。
      10、4276 The Ghost Blows Light  有两种写法,一种是把一棵树压缩成一条链,然后在链上DP,一种和 Apple tree差不多,具体见Here

 

三、删点或者删边类树形DP

      1、Hdu 3586 Information Disturbing 二分Upper power limit,然后从叶子节点向上更新,边权与limit比较再进行状态转移。解题报告Here 
      2、Poj 3107 Godfather  删点,使剩下的分支中最大的节点数最小,深搜一次记录到叶子节点距离,再进行枚举求最大值,再更新答案。解题报告Here
      3、Poj 2378 Tree Cutting 删点,使剩下的分支中有最大节点数的分支小等于总数一半,问有几种方案,和上题差不多。解题报告Here     
      4、Poj 1655 Balancing Act  删点,使剩下的分支中最大的节点数最小,深搜一次记录到叶子节点距离,再进行枚举求最大值,再更新答案。解题报告Here
      5、Poj 3140 Contestants Division  删边,求删去某条边后两个分支的最小差异值,也是深搜两次。解题报告Here
 
    这篇文章将会不断更新,以后每遇到树形DP我都会整理进这个专题,希望大家保持关注。
     本文ZeroClock原创,但可以转载,因为我们是兄弟。
分享到:
评论

相关推荐

    leetcode递归专题-leetcode:不定期发布leetcode解题思路和代码

    树形DP 树 二叉树 前缀树 -- 其他树上问题 ---- ---- ---- ---- ---- ---- ---- ---- ---- 图 拓扑排序 最小生成树 最短路 联通分量 二分图 网络流 搜索 暴力搜索 DFS BFS 数组 其他算法/数据结构 位运算 并查集 二...

    2020_CSP-J、CSP-S注意事项-2021-10-03(C).pdf

    * 第4题:最后一道题绝对是压轴题,要么是剪枝的搜索,要么是动态规划,甚至还有状压DP、树形DP之类的 学习CSP-J和CSP-S需要系统地进行相关知识的学习,坚持每周做题,集中强化训练,学习重要知识点,掌握程序思想...

    USACO月赛题解1

    【USACO月赛题解1】中的知识点涵盖了多种算法和问题解决策略,适用于计算机科学,尤其是算法竞赛。以下是对各个题目及其所涉及算法的详细解释: 1. **Fiber Communications** - 这是一个并查集(Disjoint Set Union...

    ProblemSolve:2020算法研究

    :ledger: 如何进行每周选择一个主题(DP,BFS等)来解决问题选择并上传后,每人每周有1个问题每周上传代码和说明解决您要使用的语言使用Github 叉库。 解决问题并以问题为单位予以解决。 上载到src/개인 폴더/ 。 ...

Global site tag (gtag.js) - Google Analytics