URAL - 1039K - Anniversary Party(30)（树形dp简单）

K - Anniversary Party(30)

Background

The president of the Ural State University is going to make an 80'th Anniversary party. The university has a hierarchical structure of employees; that is, the supervisor relation forms a tree rooted at the president. Employees are numbered by integer numbers in a range from 1 to N, The personnel office has ranked each employee with a conviviality rating. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.

Problem

Your task is to make up a guest list with the maximal conviviality rating of the guests.

Input

The first line of the input contains a number N. 1 ≤ N ≤ 6000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from –128 to 127. After that the supervisor relation tree goes. Each line of the tree specification has the form

<L> <K>

which means that the K-th employee is an immediate supervisor of L-th employee. Input is ended with the line

0 0

Output

The output should contain the maximal total rating of the guests.

Example

input	output
`7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0`	`5`

题意：

给出n个人的活跃度，以及n个人之间的上下级关系。从这n个人中选取某些人参加聚会，使得活跃度尽量大。但是如果a参加了，他的直属上级就不能参加了；

思路：

n个人的关系构成了一个树形关系（有向：上级——>下级），最高领导就是树根；那么我们可以先从根开始，那么这时就有两种状态，我们可以选这个人（那他的直属下级就不能选），如果不选（那么他的直属下属就有两种状态可选，选和不选）；然后从树根往叶子方向走，回溯时跟新根节点的值就好，为了降低复杂度可以记忆化；个人感觉其实和数塔差不多；

这里我用dp[s][1]表示选s节点的最大值，dp[s][0]表示不选s节点的时候的最大值，再用一布尔个变量表示当前节点的状态。

其它细节代码中说吧；

代码是自己瞎写的，虽然不怎好，但是我觉得对与自己挺好理解的：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1000 * 6 + 10;
int n, dp[maxn][3], a[maxn], vis[maxn];
vector<int>v[maxn];			//存上下级的关系

int dfs(int s, bool f) {     //s：当前的节点  f：s节点的状态 true表示是可选状态，false表示不可选状态
	if (f) {				//可选状态
							//因为s为可选状态，所以分选和不选取计算
		if (dp[s][0] == 0) {		//计算不选  如果dp[s][0]>0的话，说明已经计算过了，直接使用即可
			for (int i = 0; i < v[s].size(); i++) {
				dp[s][0] += max(dfs(v[s][i], false), dfs(v[s][i], true));  //因为s不选，所以他的下级有两种状态，我们选最大的一个；
			}
		}
		if (dp[s][1] == 0) {		//选取s 同理大于0就直接使用
			for (int i = 0; i < v[s].size(); i++) {
				dp[s][1] += dfs(v[s][i], false);	//因为已经选取，所以他的子节点都不能选；
			}
			dp[s][1] += a[s];       //既然选取了s，那就加上s这个节点的值
		}
		return max(dp[s][0], dp[s][1]);      //我们选取值最大的一种状态返回
	}
	else {                    //不可选状态
		if (dp[s][0])return dp[s][0];   //如果已经有值得话就直接返回
		for (int i = 0; i < v[s].size(); i++) {
			dp[s][0] += max(dfs(v[s][i], false), dfs(v[s][i], true));   //加上子节点两种状态中最大的一种
		}
		return dp[s][0];
	}
}

int main() {

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", a + i);
	memset(vis, 0, sizeof(vis));
	memset(dp, 0, sizeof(dp));

	int a, b;
	while (scanf("%d%d", &a, &b) == 2 && a + b)v[b].push_back(a), vis[a] = 1; //vis[a]表示a是有上级的

	int root = 1;
	while (vis[root])root++;   //寻找根节点，根节点因为没有上级了，所以没有被vis标记过

	printf("%d\n", dfs(root, true));  //刚开始根节点我们可选可不选，所以为true

	return 0;
}

补：

感叹大佬的代码简洁，学不来：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1000 * 6 + 10;
int n, dp[maxn][3], a[maxn], vis[maxn];
vector<int>v[maxn];			//存上下级的关系

void dfs(int s) {    
	dp[s][0] = 0;
	dp[s][1] = a[s];
	for (int i = 0; i < v[s].size(); i++) {
		int k = v[s][i];
		dfs(k);
		dp[s][0] += max(dp[k][0],dp[k][1]);
		dp[s][1] += dp[k][0];
	}
}

int main() {

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", a + i);
	memset(vis, 0, sizeof(vis));
	memset(dp, 0, sizeof(dp));

	int a, b;
	while (scanf("%d%d", &a, &b) == 2 && a + b)v[b].push_back(a), vis[a] = 1; //vis[a]表示a是有上级的

	int root = 1;
	while (vis[root])root++;   

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

	return 0;
}