题目的意思是举办一个聚会,给出n个人,每个人有一定的幸福值,给出每个人的上级关系,对于直接的上下级关系,如果下级参加了上级不能参加,如果上级参加了下级不能参加。求举办这次聚会总幸福值最大数。


上下级很容易想到树型,所以我们需要找到根节点,设dp[i][0]代表第i个人不去,dp[i][1]代表第i个人去,递推式如下:

dp[u][0]+=max(dp[v][0], dp[v][1]);   //如果当前这个人不去,那么他应该是取他每个下级去还是不去的的最大值之和。

dp[u][1]+=dp[v][0];                         //如果这个人去,那么他应该取他每个下级不去的和。


代码:

StatusAccepted
Time124ms
Memory2008kB
Length962
LangC++
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 6005;
int n, res[maxn], in[maxn], dp[maxn][2], root;
vector<int> go[maxn];
inline int max(int a, int b){return a>b?a:b;}
void dfs(int u){
    dp[u][0]=0;
    dp[u][1]=res[u];
    for(int i=0;i<go[u].size();i++){
        int v=go[u][i];
        dfs(v);
        dp[u][0]+=max(dp[v][0], dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main()
{
    while(~scanf("%d", &n)){
        for(int i=1;i<=n;i++){
            scanf("%d", &res[i]);
            dp[i][0]=dp[i][1]=0;
            go[i].clear();
            in[i]=0;
        }
        int l, k;
        while(scanf("%d%d", &l, &k)&&l!=0&&k!=0){
            in[l]++;
            go[k].push_back(l);
        }
        for(int i=1;i<=n;i++){
            if(!in[i]){
                root=i;break;
            }
        }
        dfs(root);
        printf("%d\n", max(dp[root][0], dp[root][1]));
    }
    return 0;
}