HDU 1520 Anniversary party (樹形DP)

轉載請注明出處：憶夢http://blog.csdn.net/yimeng2013/article/details/10266765

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1520

題目大意：Ural State University要慶祝她的80年校慶，想邀請她的員工來參加，每一個員工都是有一個快樂值，最重要的是規定了邀請的員工之間不能有直接的上下級關系，求邀請到的員工最大的快樂值。

題解：最基礎的樹形dp，也是本屌第一次做樹形dp的題目.              一共就兩種狀态，root不被邀請參加和root被邀請參加，标記這兩種狀态為dp[root][0],dp[root][1]。             ①root被邀請參加的話，root的孩子就不能被選擇了，就轉化為選取root孩子中狀态為0的最大值。             ②root不被邀請參加的話，注意這裡可以選root的孩子也可以不選，是以就轉化為加上root所有孩子中被選或者不被選兩者間的最大值。             話不多說，請看代碼。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define N 6005
int dp[N][2];
struct Node
{
	int parent;
	vector<int>son;
}Node[N];

void dfs(int root)
{
	int len = Node[root].son.size();
	for(int i = 0; i < len; i++)
		dfs(Node[root].son[i]);


	for(int i = 0; i < len; i++)
	{
		dp[root][0] += max(dp[Node[root].son[i]][1],dp[Node[root].son[i]][0]);
		dp[root][1] += dp[Node[root].son[i]][0];
	}
}

int main ()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", &dp[i][1]);
			Node[i].parent = -1;
			Node[i].son.clear();
		}

		int a, b;
		while(scanf("%d %d", &a, &b), a+b)
		{
			Node[a].parent = b;
			Node[b].son.push_back(a);
		}
		
		int root = 1;
		while(Node[root].parent != -1)
			root = Node[root].parent;

		dfs(root);
		printf("%d\n",max(dp[root][1],dp[root][0]));
	}
	return 0;
}