题解 P1352 【没有上司的舞会】

你是总总 · 2017-11-08 20:27:19 · 题解

树形DP

我的f[0][i]表示i不取时开心值最大是多少

f[1][i]则表示i取时开心值最大是多少

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int f[5][6000];
int n,a,b,root;
int ne[12000],po[12000],ru[12000];
void dp(int x)
{
    for(int i = po[x];i;i = ne[i])
    {
        dp(i);
        f[1][x] = max(max(f[1][x],f[0][i]+f[1][x]),f[0][i]);//这一个点选的时候转移：可以不选子节点，可以是子节点不选时最大值+自己的值，可以是只是子节点不选时的最大值
        f[0][x] = max(max(f[0][x],f[1][i]+f[0][x]),max(f[1][i],f[0][i]));//这一个点不选的时候转移：可以是自己，可以是子节点也不选，可以是子节点选时+自己，可以是仅仅子节点选时最大
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
     scanf("%d",&f[1][i]);
    for(int i = 1;i <= n;i ++) 
     {
         scanf("%d%d",&b,&a);
         ru[b] ++;
         ne[b] = po[a]; //原理与邻接表类似  只是里面存储的都是点  可手动模拟一下
         po[a] = b;
     }
    for(int i = 1;i <= n;i ++)
     if(ru[i] == 0) 
       {
            root = i;//找树的根
            break;
       } 
    dp(root);   
    printf("%d",max(f[1][root],f[0][root]));
    return 0;
}