[ACM] POJ 2342 Anniversary party （树形DP入门题）

Description

Input

Output

Sample Input

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

Sample Output

5

Source

题意为有n个人要开一个PARTY，编号1到n，每个人都有一个欢乐值，并且每个人都有一个直接上司，为了让气氛更好，要求在这n个人中选一些人去参加PARTY，并且选出的这些人中任意两个人之间都没有直接上司或直接下属关系，求选出人的最大欢乐值。

这n个人通过直接上司或直接下属关系构成了一棵树，如果把父节点看做直接上司，那么子节点为下属，而且上司和下属不能同时选择。

定义dp[i][0] 为第i个人不选择所获得的最大欢乐值,dp[i][1] 为第i个人被选择所获得的最大欢乐值

假设 j 是第i个人的下属， 那么有转移方程  ：

dp[i][0]+=max( dp[j][0],dp[j][1]);  注意是+=，因为一个父节点有多个子节点

dp[i][1]+=dp[j][0];

用DFS遍历这棵树，每个顶点被访问，且只被访问一次。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=6005;
vector<int>son[maxn];
bool vis[maxn];
int dp[maxn][2];
int n;

void dfs(int root)
{
    vis[root]=1;
    for(int i=0;i<son[root].size();i++)
    {
        int v=son[root][i];
        if(!vis[v])
        {
            dfs(v);
            dp[root][1]+=dp[v][0];
            dp[root][0]+=max(dp[v][0],dp[v][1]);
        }
    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=n;i++)
            son[i].clear();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&dp[i][1]);
            dp[i][0]=0;
        }
        int fa,so;
        while(scanf("%d%d",&so,&fa)!=EOF)
        {
            if(so==0&&fa==0)
                break;
            son[fa].push_back(so);
            son[so].push_back(fa);
        }
        dfs(1);
        cout<<max(dp[1][0],dp[1][1])<<endl;
    }
    return 0;
}

[ACM] POJ 2342 Anniversary party （树形DP入门题）

原文：http://blog.csdn.net/sr_19930829/article/details/40537507