P1352 没有上司的舞会

题目链接https://www.luogu.org/problem/show?pid=1352
题目描述

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

输入输出格式

输入格式:
第一行一个整数N。(1<=N<=6000)

接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0 0

输出格式:
输出最大的快乐指数。

输入输出样例

输入样例#1:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
输出样例#1:
5

#include<iostream>
#include<cstring>
#include <cstdio>
using namespace std;
int father[6005],vis[6005],dp[6005][2],t;  
void dfs(int u){
    vis[u]=1;
    for(int i=1;i<=t;i++){
        if(father[i]==u&&!vis[i]){
            dfs(i);
            dp[u][1]+=dp[i][0];
            dp[u][0]+=max(dp[i][0],dp[i][1]);
        }
    }
}
int main(){
    int i,j,l,k,root;  
    scanf("%d",&t);
        for(i = 1;i<=t;i++)  
        scanf("%d",&dp[i][1]);  
        root = 0;  
        while(scanf("%d%d",&l,&k),l+k>0)  
        {  
            father[l]=k;
            root=k;  
        }  
        memset(vis,0,sizeof(vis));  
        dfs(root);  
        printf("%d\n",max(dp[root][1],dp[root][0]));  
    return 0;
}

树形dp练习题

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-23 17:45
武汉商学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议