没有上司的舞会

描述

某大学有N个职员,编号为1~N。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数Ri,但是呢,如果某个职员的上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。

输入

第一行一个整数N。(1<=N<=6000)
接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0 0

输出:

输出最大的快乐指数。

样例

  • Input
    7
    1
    1
    1
    1
    1
    1
    1
    1 3
    2 3
    6 4
    7 4
    4 5
    3 5
    0 0
  • Output
    5

思路

  • 树形dp是建立在树这种数据结构上的dp,一般状态比较好想,通过dfs维护从根到叶子或从叶子到根的状态转移。
  • 用dp[i][0]表示不选i结点的最优结果,dp[i][1]表示选i结点的最优结果
    则:1.dp[fa][0]+=max(dp[son][1],dp[son][0])
    2.dp[fa][1]+=max(dp[son][0])
    通过dfs从下往上遍历树的节点,通过子节点更新父节点,最后max(dp[root][0],dp[root][1])就是答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define LL long long int
using namespace std;
const int MAX=0x7fffffff;
const int MIN=-0x7fffffff;
const int INF=0x3f3f3f3f;
const int Mod=1e9+7;
const int MaxN=1e7+7;
int val[6001];
int f[6001];
int dp[6001][2];
int vis[6001];
vector<int>tree[6001];
void dfs(int fa){
dp[fa][1]=val[fa];
vis[fa]=1;
for(int i=0;i<tree[fa].size();i++){
int son=tree[fa][i];
if(vis[son])continue;
dfs(son);
dp[fa][1]+=dp[son][0];
dp[fa][0]+=max(dp[son][0],dp[son][1]);
}
return ;
}
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;
while(cin>>n){
INIT(f,-1);INIT(dp,0);INIT(vis,0);INIT(val,0);
for(int i=1;i<=n;i++){
cin>>val[i];
tree[i].clear();
}
int fa,z;
while((cin>>fa>>z)&&(fa!=0&&z!=0)){
f[fa]=z;
tree[z].push_back(fa);
}
int t=1;
while(f[t]!=-1) t=f[t];
dfs(t);
cout<<max(dp[t][0],dp[t][1])<<endl;
}

return 0;
}
Donate comment here