ural 1018 Binary Apple Tree(树形dp | 经典)

发布时间:2016-12-10 22:51:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"ural 1018 Binary Apple Tree(树形dp | 经典)",主要涉及到ural 1018 Binary Apple Tree(树形dp | 经典)方面的内容,对于ural 1018 Binary Apple Tree(树形dp | 经典)感兴趣的同学可以参考一下。

本文出自   http://blog.csdn.net/shuangde800 --------------------------------------------------------------------------------- 题目链接:  url-1018 题意    给一棵边有权值的二叉树,节点编号为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) 代码

上一篇:
下一篇:数据库的垂直划分和水平划分

相关文章

相关评论