转自:http://blog.csdn.net/woshi250hua/article/details/7644959
树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树、三叉树、静态搜索树、AVL树,线段树、SPLAY树,后缀树等等..
枚举那么多种数据结构只是想说树方面的内容相当多,本专辑只针对在树上的动态规划,即树形DP.做树形DP一般步骤是先将树转换为有根树,然后在树上进行深搜操作,从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分,这个也没一般性的东西可讲,因为每道题目要求做的事都不尽相同。
这个专辑暂时氛围3哥部分,分的可能不是很好,后面题目做多了理解更深了可能会更改,但那都是后话了。
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 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
4、Poj 1655 Balancing Act 删点,使剩下的分支中最大的节点数最小,深搜一次记录到叶子节点距离,再进行枚举求最大值,再更新答案。解题报告Here
这篇文章将会不断更新,以后每遇到树形DP我都会整理进这个专题,希望大家保持关注。
本文ZeroClock原创,但可以转载,因为我们是兄弟。
相关推荐
暂时看的一个比较好地讲解树形DP的课件,对初步了解树形DP有帮助
蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A...
NOIP 提高2_树形DP
DP_MassStorage_wnt5_x86-32_1412115,AHCI驱动包DP_MassStorage_wnt5_x86-32_1412115,AHCI驱动包
区间DP概率DP树形DP插头DP,每种DP一道典型例题,有助于初学者
ProfibusDP_DPV0协议 从站测试例程; 个人原创基于STM32单片机, 纯软件实现ProfibusDP_DPV0从站的功能。 2020年12月12日 温馨提示: 1.在UsartInit()初始化函数中,将Usart1Init(); 这一行调整到m_ProfibusDpPar....
DP_MassStorage_wnt5_x86-32_1209,集成驱动的必备工具,使用里边的7z压缩文件
DP_MassStorage DP_MassStorage
SATA驱动包_XP原版集成SATA驱动_DP_MassStorage_wnt5_x86-32_805.7z
DP_DIA_1_通讯例程rar,DP_DIA_1_通讯例程
DP_WebCam_wnt6-x86_1101
蓝牙协议栈之一,a2dp协议特征说明文档和开发文档,需要用到蓝牙音频传输的可以参考
DP_MassStorage_wnt5_x86-32_1101
ACM之树形DP,利用子节点的信息维护父节点信息,想在区域赛拿奖的童鞋就抱走吧
07 树形DP一、没有上司的舞会题目链接::f[u]
DP_MassStorage_20064.7z
PROFIBUS-DP简介。介绍了PROFIBUS-DP的发展,协议规则,是开发PROFIBUS-DP现场总线基础。
2021 最新 NOIP 学习课件:树形dp,欢迎大家下载学习
由大师制作的状态压缩算法的入门资料为初学者介绍状态压缩DP相关算法并提供解题思路共47页,讲解到位 题题经典
背包DP与树形DP从零起步,形象讲解让你更了解DP