舞会)"/>
[树形DP] 猴腮雷 (没有上司的舞会)
题目描述 Description
新年就要来临啦,小猴腮雷一家 N N N人将作为嘉宾被邀请到了春晚上。然而小猴腮雷的一家都曾经是大名鼎鼎的熊孩子,无论在什么时候都会,也只会和自己的直系亲属,也就是父母吵架,当然,即便是在春晚这个舞台上也是这样。为了到时候不会引起战争,组委会据此思考到底要邀请哪些人?更让组委会头疼是,每个猴腮雷拥有一个活泼值 A i A_i Ai,组委会既想要他们不会发生矛盾,也想尽量让来参加的猴腮雷活泼值的和最大?
输入 Input
第一行一个整数 N N N。
接下来 N N N行,第 i + 1 i+1 i+1行表示 i号猴腮雷的活泼值 A i A_i Ai。
接下来 N − 1 N-1 N−1行,每行输入一对整数 L , K L,K L,K。表示 K K K和 L L L是直接亲属关系。
最后一行输入 0 0 0\ 0 0 0。
输出 Output
一行整数表示最大的活泼值的和。
样例输出 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
限制 Limits
对于 70 % 70\% 70%的数据 1 ≤ N ≤ 1000 1\le N\le 1000 1≤N≤1000
对于 100 % 100\% 100%的数据 1 ≤ N ≤ 6000 , − 128 ≤ A i ≤ 127 1\le N\le 6000, -128\le A_i\le 127 1≤N≤6000,−128≤Ai≤127
Time Limits : 1s & Memory Limit : 128MB
经典树形DP题,记 d p x , 0 / 1 dp_{x,0/1} dpx,0/1为猴腮雷 x x x不来/来的情况,根据这个就能推出DP方程了:
d p x , 0 = ∑ s o n ∈ x max { d p s o n , 0 , d p s o n , 1 } d p x , 1 = h a p p y x + ∑ s o n ∈ x d p s o n , 0 dp_{x,0}=\sum\limits_{son\in x}\max\{ dp_{son,0},dp_{son,1}\} \\ dp_{x,1}=happy_x+\sum\limits_{son\in x}dp_{son,0} dpx,0=son∈x∑max{dpson,0,dpson,1}dpx,1=happyx+son∈x∑dpson,0
答案是 max { d p 1 , 0 , d p 1 , 1 } \max\{dp_{1,0},dp_{1,1}\} max{dp1,0,dp1,1}。
时间复杂度 O ( n ) O(n) O(n)。
Code
更多推荐
[树形DP] 猴腮雷 (没有上司的舞会)
发布评论