P1052 （C++代码）

解题思路:





注意事项:





参考代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e3+10;
int n;
int dp[maxn][2];//记录状态 
int hap[maxn];//快乐值 
bool no_head[maxn];//记录是否是校长 true->不是 
vector<int>down[maxn];//记录每个人的下属 
int dfs(int now,bool if_get)
{    
    if(dp[now][if_get]) return dp[now][if_get];    //递归终点 
    if(!down[now].size()) return hap[now]*if_get;    //只有参加，才能贡献快乐值 
    int res=0;    
    if(if_get){        
    for(int i=0;i<down[now].size();i++){            
    int &nxt=down[now][i];
    res+=dfs(nxt,false);
        }
    }    
    else
    {       for(int i=0;i<down[now].size();i++){            
            int &nxt=down[now][i];
            res+=max(dfs(nxt,true),dfs(nxt,false));            //下属参加或不参加的最大值才是最佳贡献 
        }
    }    
        return dp[now][if_get]=if_get?res+hap[now]:res;    //如果这个人参加，不要忘了返回他自身的快乐值 }int main(){    cin>>n;    for(int i=1;i<=n;i++) scanf("%d",&hap[i]);    int a,b;    while(scanf("%d%d",&a,&b)&&a&&b){
        down[b].push_back(a);
        no_head[a]=true;
    }    
        for(int i=1;i<=n;i++) if(!no_head[i])   
        cout<<max(dfs(i,false),dfs(i,true));    
        return 0;
}