BZOJ 2809 [Apio2012]dispatching

发布于 2017-05-23  146 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2809

题意:一棵有根树,树上每个节点都有一个费用和一个领导力,对于每个节点的子树,可以在总费用≤m 的情况下选择若干个节点,那么该节点的价值是领导力*选择节点数量... 求最大价值...


这个题意貌似能看了 orz

在确定选择的领导节点的情况下怎么处理呢?显然贪心的去选费用尽可能低的节点更优,对于怎么找出最优的那些节点,维护优先队列找出即可,但是这样的复杂度是不能接受的。

刚刚的操作需要我们在每个节点都重新考虑一次,并没有用上已经考虑过的节点的相关信息,那么我们考虑在已知子节点的情况下如何找出父节点的答案呢,很显然,我们合并它的子节点所维护的大根堆,若不合法,删除费用最高的节点直至合法即可,因为那些节点一定是没有用的了,这样只要一发可并堆即可,还是比较裸的... 需要注意的是要开 long long...1A 啦啦啦

 

 


一个非常弱的准退役OIER