本文出自 http://blog.csdn.net/shuangde800
---------------------------------------------------------------------------------
题意
给一棵边有权值的二叉树,节点编号为1~n,1是根节点。求砍掉一些边,只保留q条边,这q条边构成的子树
的根节点要求是1,问这颗子树的最大权值是多少?
思路
非常经典的一道树形dp题,根据我目前做过的题来看,有多道都是由这题衍生出来的。
f(i, j) 表示子树i,保留j个节点(注意是节点)的最大权值。每条边的权值,把它看作是连接的两个节点中的儿子节点的权值。
那么,就可以对所有i的子树做分组背包,即每个子树可以选择1,2,...j-1条边分配给它。
状态转移为:
f(i, j) = max{ max{f(i, j-k) + f(v, k) | 1<=k<j} | v是i的儿子}
ans = f(1, q+1)
代码
<script src="https://code.csdn.net/snippets/787.js" type="text/javascript"></script>
分享到:
相关推荐
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
URAL3D
Pascal acm_timus_ural_1148.pas
URAL(Timus Online Judge)部分测试数据 不全
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
Pascal acm_timus_ural_1099.pas
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
乌拉尔
资源分类:Python库 所属语言:Python 资源全名:ural-0.25.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....