P1352 没有上司的舞会

àì夳堔傛蜴生んèń 2023-06-02 10:50 7阅读 0赞

# P1352 没有上司的舞会 #

时间限制1.00s

内存限制125.00MB

### 题目描述 ###

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

### 输入格式 ###

第一行一个整数N。(1<=N<=6000)

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

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

最后一行输入0 0

### 输出格式 ###

输出最大的快乐指数。

### 输入输出样例 ###

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

\--------------

5
    
    这道题是一道很经典的树形dp，（经典到我这个对dp一窍不通的人都一眼就看出来了）
    很明显，这里面的职员有 来/不来 两种选择，所以用一个dp数组记录最大快乐值
    dp[i][0]表示以节点i为根的子树中，i号职员不来（不取树根i）
    dp[i][1]表示以节点i为根的子树中，i号职员来（取树根i）
    当一个人来了后，他/她与他/她的下属们组成的树的最大值就相当于dp[u][1];
    但是这个人的直接下属们肯定不会来了，所以dp[u][1]=a[u]+dp[v1][0]+dp[v2][0]......;
    （v1，v2...表示u的几个儿子    a[u]表示u的快乐度）
    当一个人不来了，他/她与他/她的下属们组成的树的最大值就相当于dp[u][0];
    但是这个人的直接下属们可以来也可以不来，所以dp[u][0]=max(dp[v1][0],dp[v1][1])+max(dp[v2][0],dp[v2][1])+......;
    （v1，v2...表示u的几个儿子 a[u]表示u的快乐度） 整理一下dp方程：

dp[x][1]=a[x];
    dp[x][0]=0;
    for(int i=head[x];i;i=nxt[i])
    {
    	int v=to[i];
    	if(v==fa_) continue;
    	dfs(v,x);
    	dp[x][0]+=max(dp[v][1],dp[v][0]);
    	dp[x][1]+=dp[v][0];
    }

最后，可以上完整代码了：

#include<bits/stdc++.h>
    using namespace std;
    int head[200010],to[200010],nxt[200010],tot=1,n;
    int dp[6005][2];
    int a[6005];
    bool book[6005];
    void add(int x,int y) 
    {
        to[tot]=y;
        nxt[tot]=head[x];
        head[x]=tot++;
    }
    void dfs(int x,int fa_)
    {
    	dp[x][1]=a[x];
    	dp[x][0]=0;
    	for(int i=head[x];i;i=nxt[i])
    	{
    		int v=to[i];
    		if(v==fa_) continue;
    		dfs(v,x);
    		dp[x][0]+=max(dp[v][1],dp[v][0]);
    		dp[x][1]+=dp[v][0];
    	}
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        } 
        int x,y;
       	while(1)
        {
        	scanf("%d%d",&x,&y);
        	if(!x &&!y) break;
        	add(y,x);
        	book[x]=1;
    	}
    	int xy=1;
    	for(int i=1;i<=n;i++) if(!book[i]) xy=i;
    	dfs(xy,0);
    	printf("%d",max(dp[xy][0],dp[xy][1]));
        return 0;
    }

转载于:https://www.cnblogs.com/chen-1/p/11326838.html