hdu1520 Anniversary party 【树形DP入门】

题目链接：传送门

有n个员工，每个员工的有直接上属或者直接下属，一个聚会，要求到场的员工之间不能有直接的上下属关系，每个员工有到场的快乐程度，请问怎么选快乐程度最大？

题解：

所有人的关系最后化为一棵树，在树在进行dp，取最优，这里面一定会有至少一个员工没有直接上属，对他进行dfs，进行递归操作

dp数组的关系 的dp[n][1]代表这个人到场  dp[n][0]代表这个人没到场

dp状态转移方程式为：

    dp[x][0] += max(dp[v][1], dp[v][0]);
    dp[x][1] += dp[v][0];

AC_code：

#include<bits/stdc++.h>
#define ll long long
#define maxn 6005
#define line printf("------------------\n");
using namespace std;

vector<int> vec[maxn];
int val[maxn];
int vis[maxn], dp[maxn][2], in[maxn];
void dfs(int x) {
	dp[x][0] = 0;
	dp[x][1] = val[x];
	vis[x] = 1;
	for(int i = 0; i < vec[x].size(); i++) {
		int v = vec[x][i];
		if(!vis[v]) {
			dfs(v);
			dp[x][0] += max(dp[v][1], dp[v][0]);
			dp[x][1] += dp[v][0];
		}
	}
}

int main() {
	int n;
	while(~scanf("%d", &n)) {
		for(int i = 0; i <= n; i++) {
			vec[i].clear();
		}
		for(int i = 1; i <= n; i++) {
			scanf("%d", &val[i]);
		}
		memset(in,0,sizeof(in));
		int x, y;
		while(~scanf("%d%d", &x, &y)) {
			if(x==0 && y==0) {
				break;
			}
			vec[y].push_back(x);
			in[x]++;
		}
		for(int i = 1; i <= n; i++) {
			if(!in[i]) {
				memset(vis, 0, sizeof(vis));
				memset(dp, 0, sizeof(dp));
				dfs(i);
				printf("%d\n",max(dp[i][1], dp[i][0]));
				break;
			}
		}
	}

	return 0;
}