1380 没有上司的舞会
1380 没有上司的舞会
HansBug
发布于 2018-04-10 16:48:43
发布于 2018-04-10 16:48:43
1380 没有上司的舞会
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
输入描述 Input Description
第一行一个整数N。(1<=N<=6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。
输出描述 Output Description
输出最大的快乐指数。
样例输入 Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
各个测试点1s
分类标签 Tags 点此展开
题解：额。。最近快要省选了，感觉自己太弱，来发水题增加点信心（HansBug：其实是好久没打树形DP了有木有）。这题别的没啥，是一棵树，不是森林，而且有唯一的根节点，这就不难办了（假如是个根节点不唯一的有向图的话还得拓扑排序，唉那样子真心神烦。。。唉这年头写个水题还得想这么多，我真心太弱了TT）
1 type
2 point=^node;
3 node=record
4 g:longint;
5 next:point;
6 end;
7 vec=record
8 a0,a1:longint;
9 end;
10 var
11 i,j,k,l,m,n:longint;
12 d1,d2:vec;
13 a:array[0..10000] of point;
14 b,c:array[0..10000] of longint;
15 function max(x,y:longint):longint;inline;
16 begin
17 if x>y then max:=x else max:=y;
18 end;
19 function min(x,y:longint):longint;inline;
20 begin
21 if x<y then min:=x else min:=y;
22 end;
23 function dp(x:longint):vec;
24 var
25 d1,d2:vec;
26 p:point;
27 begin
28 d1.a0:=0;d1.a1:=b[x];
29 p:=a[x];
30 while p<>nil do
31 begin
32 d2:=dp(p^.g);
33 d1.a0:=d1.a0+max(d2.a1,d2.a0);
34 d1.a1:=d1.a1+d2.a0;
35 p:=p^.next;
36 end;
37 exit(d1);
38 end;
39 procedure add(x,y:longint);inline;
40 var p:point;
41 begin
42 new(p);p^.g:=y;
43 p^.next:=a[x];a[x]:=p;
44 end;
45 begin
46 readln(n);
47 for i:=1 to n do readln(b[i]);
48 for i:=1 to n do a[i]:=nil;
49 fillchar(c,sizeof(c),0);
50 for i:=1 to n-1 do
51 begin
52 readln(j,k);
53 add(k,j);c[j]:=1;
54 end;
55 m:=-1;
56 for i:=1 to n do if c[i]=0 then m:=i;
57 d1:=dp(m);
58 writeln(max(d1.a0,d1.a1));
59 end.
60 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-02-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录