没有上司的舞会

· · 题解

p1352 没有上司的舞会

题目描述

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

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

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

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

最后一行输入0 0

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

————————————————————————————————————————————

读完题可以发现这就是一个树形dp;废话（详见斜体）

至于动态方程： 根据题目，无非就是取不取当前这个点；

于是可以得出以下方程：

  1. dp[x][0]+=max(dp[son][1],dp[son][0]); // 如果x不去,则快乐值为+儿子去或者不去的最大值

  2. dp[x][1]+=dp[son][0]; // 如果x去,则快乐值为+儿子不去的最大值

然后我们可以用一个vector数组表示从属关系

上代码：


#include<bits/stdc++.h>
using namespace std;
int read()//快读 
{
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
} 

vector < int > v[6010];
int r[6010];
int n,boos[6010];
int maxn=1e9;
int dp[6010][10];

void init()//读入 
{
    n=read();
    for(int i=1;i<=n;++i)
    r[i]=read();
    for(int i=1;i<=maxn;++i)
    {
        int x=read(),y=read();
        if(x==y&&x==0) break;
        boos[x]=y;
        v[y].push_back(x);//建立从属关系 
    }
}

void dfs(int x)
{
    for(int j=0;j<v[x].size();++j)
    {
        int son=v[x][j]; 
        dfs(son);
        dp[x][0]+=max(dp[son][1],dp[son][0]); //  如果x不去,则快乐值为+儿子去或者不去的最大值
        dp[x][1]+=dp[son][0]; // 如果x去,则快乐值为+儿子不去的最大值

    }
    dp[x][1]+=r[x];//记得加上x点去的快乐值 
}

void work()
{
    for(int i=1;i<=n;++i)
    {
        if(boos[i]==0)//找根节点（老板） 
        {
            dfs(i); 
            printf("%d",max(dp[i][0],dp[i][1]));
            break;
        }
    }
}

int main()
{
    init();
    work();
    return 0;
}
_________________________________________________________________