22 条题解
-
1
j18tm01 LV 10 @ 5 年前
这题好坑啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊······(省略N字)
-
17 年前@
const
maxn=4040;
maxk=550;
var
fl,fr:array[0..maxn,0..maxk]of longint;
v:array[0..maxn,0..maxn]of longint;
a,sum,f:array[0..maxn]of longint;
n,k,ans:longint;function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;procedure dfsl(x:longint);
var
i,j:longint;
begin
sum[x]:=sum[f[x]]+a[x];
for i:=1 to v[x,0] do
begin
for j:=0 to k do
fl[v[x,i],j]:=fl[x,j];
dfsl(v[x,i]);
for j:=1 to k do
fl[x,j]:=max(fl[x,j],fl[v[x,i],j-1]+a[v[x,i]]);
end;
end;procedure dfsr(x:longint);
var
i,j:longint;
begin
for i:=v[x,0] downto 1 do
begin
for j:=0 to k do
fr[v[x,i],j]:=fr[x,j];
dfsr(v[x,i]);
for j:=1 to k do
fr[x,j]:=max(fr[x,j],fr[v[x,i],j-1]+a[v[x,i]]);
end;
end;procedure main;
var
i,x:longint;
begin
read(n,k);
for i:=1 to n do
begin
read(f[i],a[i]);
inc(v[f[i],0]);v[f[i],v[f[i],0]]:=i;
end;
dfsl(1);
dfsr(1);
for i:=1 to n do
if v[i,0]=0 then
for x:=0 to k do
ans:=max(ans,fl[i,x]+fr[i,k-x]+sum[i]);
writeln(ans);
end;begin
main;
end. -
-415 年前@
顶楼下~这篇论文是徐持衡。。。
其中重点看树形依赖背包(选课)
的优化。
但是有点不同的是这题有条免费路径 -
-415 年前@
建议先看看国际集训队有一篇介绍背包的论文,特别是泛化背包,理解了那个这题理解起来方便多了……
-
-415 年前@
巧妙的状态构建和treedp优化,看了很久才明白。
虽然程序极短。 -
-415 年前@
比赛的时候一看就知道做不来....于是看都不看了
本人乃不懂树的沙茶.....于是乎挥毫泼墨
写下几行大字:
var n:longint;beginwriteln(random(n*n)+1);end.
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -
-415 年前@
30分啊顶多。。。。。。。。。。。
多了个h限制,太难了。。。。。 -
-415 年前@
被虐了。不懂做
-
-415 年前@
陶陶就是LX那位神牛吧?
-
-58 年前@
摘苹果容易吃苹果难
-
-58 年前@
摘苹果容易吃苹果难
-
-59 年前@
摘苹果容易吃苹果难
-
-510 年前@
求讲解那条免费路径是什么情况
-
-510 年前@
摘苹果容易吃苹果难
-
-512 年前@
摘苹果容易吃苹果难
-
-515 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 9ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 9ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:18ms
哈 足够快了 算法O(NK) -
-515 年前@
O(n*k^2)
前3点0ms,后7点超时……
无语ing...
TreeDp还能再优化吗?
附上我的程序:program P1676;var n,i,j,k:longint; c,h:array[1..4000] of longint; g:array[0..4000,-1..500,0..1] of longint; t:array[0..4000,0..1] of longint;procedure deep(p,q:longint);var i:longint;begin if p=0 then exit; h[p]:=q; deep(t[p,0],q+1); deep(t[p,1],q);end;function dp(p,q,r:longint):longint;var i:longint;begin if (p=0) or (q -
-515 年前@
O(N*K^2) +卡时。。
本来指望拿个40--50.。结果全部答案错误。可见我沙茶。
昨天调了2.5小时的TreeDp。。
结果。。O.O
-
-515 年前@
= =
占个楼先
-
-515 年前@
ORZ陶陶神牛
http://blog.sina.com.cn/s/blog_5dafc7f00100fopg.html
陶陶最近又长了两颗小牙齿,总共有十颗了。小宝贝喜欢吃有些硬度的食物,饼干、馒头、苹果……,尤其是苹果,她不需要我们给她弄成苹果泥了,她喜欢苹果片。我喜欢看陶陶吃苹果的样子。她拿着奶奶削好的苹果片,慢慢的放到嘴边,然后用小牙“咔嚓”咬下苹果片的一大块,发出脆脆的声音。这时,她抬头看看我,好像在对我说“妈妈,我自己吃到苹果了,真好吃!”我冲她笑笑,她也回敬我一个笑脸。可是,陶陶吃苹果并不总是这么乖。她有时吃的带劲了,一口接着一口的咬,结果嘴里的苹果还没咽下去,又吃一口,嘴里的苹果太多了,转不开个了,小家伙就急得“嗷嗷”大叫。即使这样,她也决不允许我们把她嘴里的苹果弄出来,有时真让我们着急。
陶陶是我的精灵,她带给我的快乐是永远不会忘记的!