题目描述
某大学有 N 个职员，编号为 1…N。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 R_i，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式
输入的第一行是一个整数 N。
第 2 到第 (N 1) 行，每行一个整数，第 (i 1) 行的整数表示 i 号职员的快乐指数 R_i。
第 (N 2) 到第(2N 1) 行，每行输入一对整数L,K，代表 K 是 L 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
输入输出样例
输入 #1
代码语言：javascript复制7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5输出 #1
代码语言：javascript复制5说明/提示
对于 100% 的数据，保证 1le N le 6000 , -128 le R_i le 127 , 1le L,K le N且给出的关系一定是一棵树。
分析
分析题目，我们很容易发现题目中存在两种状态——来与不来，于是我们发现当上司来的时候，所获得的最大欢乐值为上司的欢乐值 下属不来所导致的下属的下属产生的欢乐值，而当上司不来的时候，所获得的最大欢乐值为上司不来所导致的上司的下属产生的欢乐值 下属的欢乐值和下属不来所导致的下属的下属的欢乐值中的最大值
我们定义 y 表示当前处理的人的编号，x 为 y 的下属的编号，dp[y][1] 表示当前人来所获得的最大欢乐值，dp[y][0] 表示当前人不来所获得的最大欢乐值。很容易得到如下方程： dp[y][1]=dp[y][1] dp[x][0],dp[y][0]=dp[y][0] max(dp[x][0],dp[x][1])
代码
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int n,x,y,ans,dp[10001][2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i ){
scanf("%d",&dp[i][1]);
}
ans=dp[1][1];
for(int i=1;i<n;i ){
scanf("%d%d",&x,&y);
dp[y][1] =dp[x][0];
dp[y][0] =max(dp[x][0],dp[x][1]);
ans=max(ans,dp[y][1]);
ans=max(ans,dp[y][0]);
}
printf("%d",ans);
return 0;
}最后修改：2021 年 07 月 20 日 03 : 05 PM
© 允许规范转载
