1561:The more, The Better - hdu
Problem Description
ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有些城堡不能直接攻克,要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗?
Input
每个测试实例首先包括2个整数,N,M.(1 <= M <= N <= 200);在接下来的N行里,每行包括2个整数,a,b. 在第 i 行,a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡,如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。
Output
对于每个测试实例,输出一个整数,代表ACboy攻克M个城堡所获得的最多宝物的数量。
Sample Input
3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0
Sample Output
5 13
Author
8600
Source
HDU 2006-12 Programming Contest
树形依赖背包基础题
首先先讲一下泛型物品,就是这个物品并不是不变的,你给他v的花费,他给你h[v]的价值,这个大家应该很熟悉吧
然后就是树形依赖背包了,就是每个物品必须在他的父亲被选了之后才能选
一般我们用很基本的方法,就是设f[i,j]表示这颗子树用j的花费可以得到的价值,然后很容易得到一个O(n*v^2)的算法
但是如果是这样还不够好,于是就有了O(n*v)的算法
其实我们发现每个节点都是一个泛型物品,我们要做的是泛型物品的和,所以是O(v^2)的
我们有更好的做法
假设s是i的儿子我们就先给f[s]赋一个初值,强制选物品s,和f[i]合起来,这样是O(v)的,然后dfs(s),然后再O(v)求f[i]和f[s]的并
这样做就是O(n*v)的啦
const
maxn=;
var
f:array[..maxn,..maxn]of longint;
first,last,next,a:array[..maxn]of longint;
n,m,tot:longint; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end; procedure dfs(x,m:longint);
var
i,j:longint;
begin
i:=first[x];
while i<> do
begin
for j:= to m- do
f[last[i],j]:=f[x,j];
dfs(last[i],m-);
for j:= to m do
f[x,j]:=max(f[x,j],f[last[i],j-]+a[last[i]]);
i:=next[i];
end;
end; procedure main;
var
i,x:longint;
begin
for i:= to n do first[i]:=;
tot:=;
for i:= to n do
begin
read(x,a[i]);
insert(x,i);
end;
for i:= to m do f[,i]:=;
dfs(,m);
writeln(f[,m]);
read(n,m);
end; begin
read(n,m);
while n<> do
main;
end.
最新文章
- Java正则速成秘籍(二)之心法篇
- [Android]快捷键
- CSS3 Media Queries实现响应式布局
- java中post时中文乱码
- ZOJ 3811 Untrusted Patrol
- hdu 2041 超级楼梯
- 【BZOJ】【2661】【Beijing WC2012】连连看
- poj2942 Knights of the Round Table 双连通分支 tarjan
- Bash常用快捷键
- java常识和好玩的注释
- OSCHina技术导向:Java全文搜索框架Lucene
- iOS中有关配置 Apache 服务器的详细步骤
- 【C语言的日常实践(十四)】constkeyword详细解释
- spark-2.0.0与hive-1.2.1整合
- 利用proxychains在终端使用socks5代理
- iOS开发 Android开发 移动Web开发
- 201521123045 《JAVA程序设计》第1周学习总结
- 选择排序—堆排序(Heap Sort) 没看明白,不解释
- Android下实现手机验证码
- MFC 解决中文乱码问题