0%

题解 P1352【没有上司的舞会】

P1352 没有上司的舞会

本蒟蒻的第一篇题解~

题面

题目描述

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

输入格式

输入的第一行是一个整数n(1n6000)

2到第(n+1)行,第(i+1)行的整数表示i号职员的快乐指数ri(128ri127)

(n+2)到第2n行,每行输入一对整数l,k,代表kl的直接上司。

输出格式

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

解析

我刚学树形dp写对了一道题就来写题解

定义数组f[maxn+1][2],其中f[x][0]表示以x为子树树根的子树在x不参加舞会时的最大快乐值,f[x][1]表示以x为子树树根的子树在x参加舞会时的最大快乐值。

根据题目描述可知,上司去了,下属一定不去;上司不去,下属可去可不去。则可得

f[x][1]=r[x]+yxf[y][0]

即将每个下属不去时得到的快乐值累加再加上x去时得到的快乐值

f[x][0]=yxmax(f[y][0],f[y][1])

即将每个下属去或不去得到的快乐值中选最大值再累加

得到了状态转移方程,只要找到根root,直接dfs(root)即可。

其余详见代码。

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;//f数组的意义如上所述

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]; //为了找根而开辟的数组,not_root[x]=1表示x不是根

void dfs(int x) //树形dp
{
f[x][1]=r[x]; //f[x][1]初始设置为自己的快乐值
f[x][0]=0; //f[x][0]初始设置为0
for(int i=head[x];i;i=edge[i].next){ //遍历x的连边
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); //从根开始dp
cout<<max(f[root][0],f[root][1]); //输出根节点去和不去时所得快乐值中的最大值
return 0;
}