【DP_树形DP专辑】【9月9最新更新】 - ZeroClock - 博客频道 - CSDN.NET



树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树、三叉树、静态搜索树、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原创,但可以转载,因为我们是兄弟。


Read full article from 【DP_树形DP专辑】【9月9最新更新】 - ZeroClock - 博客频道 - CSDN.NET


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts