[树形dp]没有上司的舞会

题目描述

U r a l Ural Ural 大学有 N N N 名职员，编号分别为 1 ∼ N 1 \sim N 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 H i H_i Hi​ 给出，其中 1 ≤ i ≤ N 1 \le i \le N 1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 N N N( 1 ≤ N ≤ 6000 1 \le N \le 6000 1≤N≤6000)。
接下来的 N N N 行，每行一个整数 H i H_i Hi​，表示第 i i i 名职员的快乐值 H i H_i Hi​。
接下来的 N − 1 N - 1 N−1 行，每行两个整数 a , b a, b a,b，表示 b b b 是 a a a 的直接上司。

输出格式

输出一行一个整数代表最大的快乐值。

样例

样例输入1

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

样例输出1

5

数据范围

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 6 × 1 0 3 1 \le N \le 6 \times 10 ^ 3 1≤N≤6×103， − 128 ≤ H i ≤ 127 -128 \le H_i \le 127 −128≤Hi​≤127， 1 ≤ a , b ≤ N 1 \le a, b \le N 1≤a,b≤N，且给出的关系一定是一棵树。

思路

首先，我们很容易想到使用暴力做法，使用 dfs 算法，遍历整棵树，枚举当前节点是否选取，计算快乐值。

显然，这种算法一定会超时。

由于题目在求最大的快乐值，不需要追究过程，我们可以考虑使用 dp 算法。

对于每一个节点，有两种情况：

1. 当前节点参加舞会，则其子节点不能参加舞会，将子节点不参加舞会的快乐值相加，与 0 0 0 取最大值；
2. 当前节点不参加舞会，则其子节点可以参加，也不可以参加，将每个节点的两种快乐值取最大值再相加，与 0 0 0 取最大值。

和 0 0 0 取最大值是因为可以一个人也不参加（快乐值可能小于 0 0 0）。

最后的答案是根节点两种情况的最大值。

由此，我们可以开始 dp 了。

划分阶段

用 d p dp dp 数组存储每一个节点的两种情况。

状态设计

设 d p [ x ] [ 0 / 1 ] dp[x][0/1] dp[x][0/1] 表示第 x x x 个节点是否参加舞会， 0 0 0 表示当前节点不参加， 1 1 1 表示当前节点参加。

转移方程

d p [ x ] [ 0 ] = max ⁡ ( 0 , ∑ 1 ≤ i ≤ N max ⁡ ( d p [ i ] [ 0 ] , d p [ i ] [ 1 ] ) ) dp[x][0] = \max(0, \sum_{\mathclap{1 \le i \le N}}\max(dp[i][0], dp[i][1])) dp[x][0]=max(0,1≤i≤N∑​max(dp[i][0],dp[i][1]))

d p [ x ] [ 1 ] = max ⁡ ( 0 , ∑ 1 ≤ i ≤ N d p [ i ] [ 0 ] ) + a [ i ] dp[x][1] = \max(0, \sum_{\mathclap{1\le i \le N}}dp[i][0]) + a[i] dp[x][1]=max(0,1≤i≤N∑​dp[i][0])+a[i]

a n s = max ⁡ ( d p [ r t ] [ 0 ] , d p [ r t ] [ 1 ] ) ans = \max(dp[rt][0], dp[rt][1]) ans=max(dp[rt][0],dp[rt][1])

边界条件

当递归到最底层时，即没有子节点，返回。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[6010];
vector<int> v[6010];//邻接表存图
bool fl[6010];
int f[6010][2];//dp数组
void dfs(int x){
	f[x][1] = a[x];
	f[x][0] = 0;
	for(auto i : v[x]){//遍历v[x](从v[x].begin() 到 v[x].end())
		dfs(i);
		f[x][0] += max(f[i][0], f[i][1]);
		f[x][1] += f[i][0]; 
	} 
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
		fl[i] = 1;
	}

	//连边
	while(1){
		int x, y;
		scanf("%d %d", &x, &y);
		if(x == 0 && y == 0){
			break;
		}
		v[y].push_back(x); 
		fl[x] = 0;
	}
	
	//求根节点
	int rt = 0;
	for(int i = 1; i <= n; ++ i){
		if(fl[i]){
			rt = i;
			break;
		}
	}
	
	//树形dp
	dfs(rt);
	
	printf("%d", max(f[rt][0], f[rt][1]));
	return 0;
}

感谢观看，请勿抄袭！