树形DP学习笔记

树形DP

入门模板题 poj P2342

　　大意就是一群职员之间有上下级关系，每个职员有一个快乐值，但是只有在他的直接上级不在场的情况下才会快乐。求举行一场聚会的快乐值之和的最大值。

 

求解

　　声明一个数组，f[i][j]。f[i][0]表示不邀请第i个员工时，该员工子树上的最大快乐值之和。f[i][1]则表示邀请时子树的最大快乐值之和。

 

#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 6000
using namespace std;

int n;
int fa[MAX_N+5];    //该员工的上级 
int f[MAX_N+5][3];    //f[i][0]不邀请该员工,该节点子树上的的最大快乐值  

vector<int> G[MAX_N+5];        //建图 记录该员工的下级 
int root=1;

inline int max(int a,int b){
    return a>b?a:b;
}

void dfs(int root){
    for (int i=0;i<G[root].size();i++)
        dfs(G[root][i]);
    for (int i=0;i<G[root].size();i++){
        f[root][0]+=max(f[G[root][i]][0],f[G[root][i]][1]);
        f[root][1]+=f[G[root][i]][0]; 
    }
}    
int main(){
//    freopen("test1.in","r",stdin);
    memset(fa,-1,sizeof(fa));
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&f[i][1]);
    int father,so;
    while (scanf("%d%d",&so,&father)&&father&&so){    //建图 
        G[father].push_back(so);
        fa[so]=father;
    }
    while (fa[root]!=-1)    root=fa[root];    //找到根节点 
    dfs(root);
    printf("%d",max(f[root][0],f[root][1]));
    return 0;
}

[参考《挑战程序设计》第二版及网上资料]