P1352 没有上司的舞会
本蒟蒻的第一篇题解~
题面
题目描述
某大学有个职员,编号为。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
输入格式
输入的第一行是一个整数。
第到第行,第行的整数表示号职员的快乐指数。
第到第行,每行输入一对整数,代表是的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
解析
我刚学树形dp写对了一道题就来写题解
定义数组,其中表示以为子树树根的子树在不参加舞会时的最大快乐值,表示以为子树树根的子树在参加舞会时的最大快乐值。
根据题目描述可知,上司去了,下属一定不去;上司不去,下属可去可不去。则可得
即将每个下属不去时得到的快乐值累加再加上去时得到的快乐值
即将每个下属去或不去得到的快乐值中选最大值再累加
得到了状态转移方程,只要找到根,直接即可。
其余详见代码。
Code
我知道你们只看这个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| #include<bits/stdc++.h> using namespace std;
int r[6001],head[6001],f[6001][2],cnt;
struct Edge{ int to; int next; }edge[6001];
void add_edge(int from,int to) { edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt; }
bool not_root[6001];
void dfs(int x) { f[x][1]=r[x]; f[x][0]=0; for(int i=head[x];i;i=edge[i].next){ dfs(edge[i].to); f[x][1]+=f[edge[i].to][0]; f[x][0]+=max(f[edge[i].to][0],f[edge[i].to][1]); } }
int main() { int n,i,l,k,root; cin>>n; for(i=1;i<=n;i++)cin>>r[i]; for(i=1;i<=n-1;i++){ cin>>l>>k; add_edge(k,l); not_root[l]=1; } for(i=1;i<=n;i++) if(!not_root[i]){ root=i; break; } dfs(root); cout<<max(f[root][0],f[root][1]); return 0; }
|