题意:有n个职员可以参加舞会,每个职员有一个欢乐值,职员之间就像一颗树,每个父节点都是子节点的上司,同时一个职员不可以他的直接上司一起参加,。现在选一些员工参加舞会,求参加员工的可能最大快乐值。
做法:设f[i][0]表示i代表的子树之下,i职员不参加的最大快乐值,f[i][1]表示i代表的子树之下,i职员参加的最大快乐值。则状态转移方程得
f[i][0]+=max(f[j][1],f[i][0])如果i不参加,那么他的每个儿子j可以选择参加或者不参加,累加每个儿子的较大的值。
f[i][1]+=f[j][0]如果i参加,那么它需要累加它每个儿子不参加时的最大快乐值。
然后就是从顶头上司根节点开始,深度优先遍历即可
#include<bits/stdc++.h>
using namespace std; int f[1005][2]; int val[1005]; vector<int> v[1005]; int ans; int vis[1005]; void dp(int t) { f[t][0]=0; f[t][1]=val[t]; for(int i=0;i<v[t].size();i++) { int y=v[t][i]; dp(y); f[t][0]+=max(f[y][1],f[y][0]); f[t][1]+=f[y][0]; } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1;i<=n-1;i++) { int a,b; scanf("%d%d",&a,&b); v[b].push_back(a); vis[a]=1; } int root; for(int i=1;i<=n;i++) { if(vis[i]==0) { root=i;break; } } dp(root); printf("%d",max(f[root][1],f[root][0])); }
转载于:https://www.cnblogs.com/dongdong25800/p/10834719.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100939.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...