【树形DP】没有上司的舞会

• 博客主页: https://blog.csdn.net/qq_50285142
• 欢迎点赞收藏✨关注❤留言  如有错误，敬请指正
• 虽然生活很难，但我们也要一直走下去

题意：
某大学有 n 个职员，编号为 1…n。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r i r_i ri​,但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
求邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

思路：
首先这n个用户的关系可以构成一棵树，只要选中父节点，那么父节点的子节点就不可以选，也就是父节点和子节点必选其一
树形结构求最优解考虑树形DP
节点标号可以使用数组进行存储
状态表示：状态表示类似于状态机模型
f [ i ] [ 1 ] f[i][1] f[i][1]表示选中节点i的最大值
f [ i ] [ 0 ] f[i][0] f[i][0]表示不选节点i的最大值
状态转移：
当前节点不选中可以由子节点不选中和子节点选中转移过来
f [ u ] [ 0 ] + = m a x ( f [ v ] [ 1 ] , f [ v ] [ 0 ] ) f[u][0] += max(f[v][1],f[v][0]) f[u][0]+=max(f[v][1],f[v][0])
而当前节点选中只能由子节点不选中转移过来
f [ u ] [ 1 ] + = f [ v ] [ 0 ] f[u][1] += f[v][0] f[u][1]+=f[v][0]

本题使用链式前向星存储树，做树形DP时，每次先对当前的节点的权值 *** 作，这样 f [ i ] [ 1 ] f[i][1] f[i][1]就可以进行初始化了，这样会先递归到叶子节点对叶子结点进行 *** 作，然后再对其父节点进行 *** 作。

首先我们需要找到根节点，我们用有向图来存储树，然后标记子节点是否出现，这样没有出现的节点一定是根节点

#include
using namespace std;
const int N = 6e3+5;

int h[N],w[N],ne[N],idx,e[N],n;
int f[N][2];
bool vis[N];

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dp(int u)
{
	f[u][1] += w[u];
	for(int i=h[u];~i;i=ne[i])
	{
		int v = e[i];
		dp(v);
		f[u][0] += max(f[v][1],f[v][0]);
		f[u][1] += f[v][0];
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	memset(h,-1,sizeof h);
	for(int i=1;i>u>>v;
		vis[u]=true;
		add(v,u);
	}
	int u;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			u = i;
			break;
		}
	}
	dp(u);
	cout< 
往期优质文章推荐 
 
 
C++ STL详解，超全总结(快速入门STL) 
李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）
区间贡献问题习题详解
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5432296.html