题目描述

某大学有 n 个职员,编号为 1…n。

他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。

现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 ri,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。

输入格式

输入的第一行是一个整数 n。

第 22 到第 (n+1) 行,每行一个整数,第 (i+1) 行的整数表示 i 号职员的快乐指数 ri。

第 (n+2) 到第(2n+1) 行,每行输入一对整数l,k,代表 k 是 l 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

输入输出样例

输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出 #1

5

说明/提示

对于 100% 的数据,保证 1<=n<=6000 , -128<=ri<=127 , 1<=l,k<=n且给出的关系一定是一棵树。

分析

​分析题目,我们很容易发现题目中存在两种状态——来与不来,于是我们发现当上司来的时候,所获得的最大欢乐值为上司的欢乐值+下属不来所导致的下属的下属产生的欢乐值,而当上司不来的时候,所获得的最大欢乐值为上司不来所导致的上司的下属产生的·欢乐值+max(下属的欢乐值,下属不来所导致的下属的下属的欢乐值)

​我们定义y表示当前处理的人的编号,xy的下属的编号,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])

代码

#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;
}
最后修改:2020 年 09 月 12 日 05 : 57 PM
如果觉得我的文章对你有用,请随意赞赏