没有上司的舞会|codevs1380|luoguP1352|树形DP|Elena

没有上司的舞会

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入描述 Input Description

第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

输出描述 Output Description

输出最大的快乐指数。

样例输入 Sample Input

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

样例输出 Sample Output

数据范围及提示 Data Size & Hint

各个测试点1s

一个节点的父亲就是它的直接上司，没有职员愿和直接上司一起与会就是要求节点和父节点不能同时选择，注意题目输入边的关系时输入u、v表示的是v是u的父亲。题目没有给根节点，所以我这里用边表来储存树，边读入边标记有父亲的点flag值为1，读入结束后再扫描一遍flag数组，flag值为0的节点就是根节点了，因为它没有父亲。接着我们就直接写一个函数dp根节点。

那么这个dp的递归函数该怎么写呢？我们先来想办法推出状态转移方程。

对于每个节点，我们都有取和不取两个操作。f[i][0]和f[i][1]分别表示i节点取和不取得到的最大值。虽然题目里给定点的权值范围是(-128<=Ri<=127)，但是我们要首先大胆地肯定一点：f[i][0]不可能小于0，f[i][1]不可能小于i点的权值也就是dis[i]。为什么？因为我们要求最大的价值，而如果当下面的节点权值都为负数会出现“越取越小”的情形时，我们就干脆一个节点都不取，这样子取得的价值就直接为0，f[i][1]不可能小于i点的权值也是同理：取了i点的权值后，若i的儿子权值都是负数，越取越小，则干脆不取，这样f[i][1]就会变成dis[i]，也不可能小于dis[i]。所以f[i][0]不可能小于0，f[i][1]不可能小于i点的权值也就是dis[i]。

注：edge[j].to存储的是i节点的儿子节点，详情可以看我的代码中边表的实现；0表示不取，1表示取。

因为这是树形dp，我们当然是从父亲递归到每一个儿子啦。对于每个节点，我们都有取和不取两个操作。如果i节点取的话，i节点的儿子节点就一定不能取，所以f[i][1]+=f[edge[j].to][0]。如果有人问我为什么f[i][1]是“+=”f[edge[j].to][0]而不是“=”，那我只能说：人家又不是只有一个儿子，你如果把i点取的值直接等于儿子不取的最大价值的话，那简直就是事故现场，你可以想想如果这么做你为什么有存储f[i][1]的必要，因为f[i][1]的值在f[edge[j].to][0]就存储了。而如果i节点不取的话，i节点的儿子就有了两种选择：取和不取。而对于这两种选择，我们当然选择更大的价值啦。所以f[i][0]+=max(f[edge[j].to][0],f[edge[j].to][1]);。

然后我再拿出一段代码分析一下，也就是核心代码：dp的函数：

void dp(int i)
{
　　for (int j=head[i]; j; j=edge[j].next) {//遍历每一条以i为起点的边j。
　　　　dp(edge[j].to);//先递归一下待会需要用到的儿子节点，你可以理解成准备dp需要用的东西。
　　　　f[i][1]+=f[edge[j].to][0];//这里不需要用到max函数，我前面已经解释过了最大值不可能是负数，所以不需要。这里是取i点的最大价值。
　　　　f[i][0]+=max(f[edge[j].to][0],f[edge[j].to][1]);//这是不取i点的最大价值。
　　}
　　f[i][1]+=dis[i];//1表示当前点要取，既然取了这个点，就要加上这个点的权值。
　　return;
}

还是不懂的同学可以自己拿笔和纸模拟一下，其实我的核心代码很短的。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 int read()
 7 {
 8     int f=1,x=0; char c=getchar();
 9     while (c>'9'||c<'0') {if (c=='-') f=-1; c=getchar();}
10     while (c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
11     return x*f;
12 }
13 int num_edge,head[6010],f[6010][2],n,dis[6010],u,v,gen;
14 long long MAX=1;
15 bool flag[6010];
16 struct Edge
17 {
18     int next;
19     int to;
20 }edge[6010];
21 void Add_edge(int from,int to)
22 {
23     edge[++num_edge].next=head[from];
24     edge[num_edge].to=to;
25     head[from]=num_edge;
26 }
27 void dp(int i)
28 {
29     for (int j=head[i]; j; j=edge[j].next) {
30         dp(edge[j].to);
31         f[i][1]+=f[edge[j].to][0];
32         f[i][0]+=max(f[edge[j].to][0],f[edge[j].to][1]);
33     }
34     f[i][1]+=dis[i];
35     return;
36 }
37 int main()
38 {
39     n=read();
40     for (int i=1; i<=n; i++) dis[i]=read();
41     for (int i=1; i<=n-1;i++) {
42         u=read(); v=read();
43         Add_edge(v,u);
44         flag[u]=1;
45     }
46     u=read(); 
47     v=read();
48     for (int i=1; i<=n; i++) 
49         if (flag[i]==0) {
50             gen=i;
51             break;
52         }
53     dp(gen);
54     if (f[gen][0]>f[gen][1]) printf("%d
",f[gen][0]); 
55         else printf("%d
",f[gen][1]); 
56     return 0;
57 }

没有上司的舞会

有问题可以直接在评论里面提问，有需要转载的请得到我的允许，否则按侵权处理。

Elena loves NiroBC forever!