ural 1018 Binary Apple Tree(树形dp | 经典)
2024-10-18 22:29:09
本文出自 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)
代码
最新文章
- redis 操作 list 的测试
- Shell入门教程:Shell变量
- SQLServer(MSSQL)、MySQL、SQLite、Access相互迁移转换工具 DB2DB v1.3
- Asp.net导出Excel乱码的解决方法
- arcgis ERROR:000824 该工具未获得许可
- Java static解析
- 【CCS仿真】用matlab把CCS保存的32位16进制的数据转换为十进制的数
- Arduino中的数据类型范围
- Mac上mariadb的启动与关闭
- Object类型
- 使用dojo遮罩加载进度。
- Web 前端开发者必知CSS 属性
- Windows 8.1 正式版镜像下载大全
- 卷烟厂生产管理系统基于ASP.NET
- PHP使用Apache中的ab测试网站的压力性能及mpm介绍
- Linux学习--- 宏定义下#、##的使用
- Testng用例失败重新运行
- 3 week work—Position
- Apache Hive 存储方式、压缩格式
- portable-net45+win8