`
king_tt
  • 浏览: 2083425 次
  • 性别: 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>

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics