`
king_tt
  • 浏览: 2221868 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

zoj 3201 Tree of Tree(树形背包dp)

 
阅读更多





本文出自 http://blog.csdn.net/shuangde800


--------------------------------------------------------------------------------------


题目链接 zoj-3201


题意

给一棵节点带权的树,找到一个有k个节点的子树,求这个子树的最大权值


思路

树形dp+背包。
f(i, j) 表示以i为根节点的有j个节点子树的最大权值
然后对i的每个子节点做分组背包,因为对于i的每个儿子,可以选择分配
1,2,3...j-1个节点给它

f(i, j) = max{ max{f(i, j-p) + f(v, p) | 1<=p<j} | v是i的儿子节点}

ans = max{ f[i][k] | 0<=i<n && i子树节点个数>=k }



代码

<script src="https://code.csdn.net/snippets/780.js" type="text/javascript"></script>

分享到:
评论

相关推荐

    概率dp 树形dp经典题目加解析

    在概率动态规划(概率DP)和树形动态规划(树形DP)中,我们常常会遇到求概率和求期望的问题。概率DP一般用于正向推算概率问题,而期望通常需要我们从结果逆向推算过程中的期望值。 首先来看概率DP在矩阵优化的应用...

    zoj 3663 Polaris of Pandora.md

    zoj 3663 Polaris of Pandora.md

    zoj 源码700题

    3. **算法与数据结构**:700题涵盖的范围广泛,涉及基本的排序算法(如冒泡、快速、归并排序),查找算法(如二分查找),以及高级算法如动态规划(如斐波那契数列、背包问题)、图论(如最短路径、最小生成树)、...

    zoj 1002_zoj1002_

    【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...

    zoj 题库 详细解答 解题代码

    知识点:数据结构、算法设计、树形结构、图形结构。 5. ZOJ Problem Set – 1049 I Think I Need a Houseboat 该题目主要考察了数学运算能力,要求解决 I Think I Need a Houseboat 问题。该问题的解决需要对数学...

    ZOJ1003 Crashing Balloon

    【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...

    ZOJ月赛 题解 (ZOJ Monthly, August 2014)

    3. **动态规划(DP)**:动态规划是一种强大的问题解决方法,适用于解决最优决策问题,如背包问题、最长公共子序列、矩阵链乘法等。解题报告中的DP思路通常包括状态定义、状态转移方程和边界条件。 4. **贪心算法**...

    ZOJ题目答案源码

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...

    zoj代码集合

    DP在解决复杂问题时有着广泛的应用,例如背包问题、最长公共子序列、最短路径等。代码集可能会包含各种类型的DP模板和实例解析。 3. **贪心算法**:贪心策略通常用于求解局部最优解的问题,如活动选择问题、霍夫曼...

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    zoj 700源代码

    ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...

    zoj1027解题指南

    【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...

    浙江大学ZOJ题目分类

    浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    ZOJ1805代码

    ZOJ1805代码

    zoj.rar_zoj_zoj4041

    《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...

    zoj 1003c 语言的

    zoj 1003 c语言的,要写这么多描述吗。。

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    zoj.zip_zoj

    【标题】"zoj.zip_zoj"所对应的资源是一个与ZOJ(Zhejiang Online Judge)相关的代码集合。ZOJ是浙江大学主办的一个在线编程竞赛平台,它提供了多种算法题目供用户练习和提交代码进行评测。这个压缩包很可能包含了在...

    zoj题目简单归类zoj题目简单归类

    ### ZOJ 题目简单归类解析 在IT竞赛和编程练习中,ZOJ(Zhejiang University Online Judge)平台提供了丰富的算法题目供学习者挑战和提升技能。本次解析将聚焦于部分被标记为“简单”的ZOJ题目,通过细致分析其描述...

Global site tag (gtag.js) - Google Analytics