本文出自 http://blog.csdn.net/shuangde800
题意
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛,有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
思路
树形背包的入门题。
f(i, j),表示子树i转播给j个用户的最大收益值
这题可以看作是树上的分组背包,每个子树看作是一组物品,这一组物品可以取1个,2个...j个
然后就是套用分组背包的算法了
f(i, 1) = w(i), 当点i是叶子节点时
f(i, j) = max{ f(i, j-k) + f[v][k] - w(i, v) | v是i的儿子节点, 0<=k<=j}
代码
<script src="https://code.csdn.net/snippets/627.js" type="text/javascript"></script>
分享到:
相关推荐
Poj1155 题解 , 文档 , 资料
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP 01背包问题 acm动态规划总结 PKU——DP专辑 背包之01 POJ 动态规划总结 背包之01...
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
poj.grids.cn题型汇总 Dp状态设计与方程总结 1.不完全状态记录 青蛙过河问题 利用区间dp 2.背包类问题 <1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
晒代码之二——多重背包(POJ1276)
poj 2763 程序 线段树 LCA 2000MS AC
poj分类poj分类poj分类poj分类
NULL 博文链接:https://200830740306.iteye.com/blog/603493