[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;
}