洛谷P1352《没有上司的舞会》

一月 28, 2019 3455

ProjectDP - 8

树形DP入门题

题目描述

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

输入输出格式

输入格式

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0 0

输出格式

输出最大的快乐指数。

输入输出样例

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

输出样例

1
5

解题思路

这是一道树形DP板子题。

设 f[u][0] 表示不选择 u 这个结点时的最大价值， f[u][1] 表示选择 u 这个结点时的最大价值
令 v 为 u 除父节点以外的邻接点，那么我们就能写出这样的伪代码

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
\text{Algorithm 1: DFS(u)}
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
1: f[u][0] = 0
2: f[u][1] = value[u]
3: \text{while u} 有未被遍历的出边 (u,v) \text{ do}
4:      \text{DFS}(v)
5:      f[u][0] = f[u][0] + \text{max}(f[v][0], f[v][1])
6:      f[u][1] = f[u][1] + f[v][0]
7: \text{end while}
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯

最后答案即为 \text{max}(f[root][0], f[root][1])

代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//
//  8.cpp
//  ProjectDP
//
//  Created by HandwerSTD on 2019/1/28.
//  Copyright © 2019 Handwer STD. All rights reserved.
//

#include <iostream>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 6000 + 10;

/*
 *
 * dp[u][true]: Choose Node[u]
 * dp[u][false]: Don't choose Node[u]
 *
 */

int val[MAXN], n;
int dp[MAXN][2], inDegree[MAXN];
std::vector<int> head[MAXN];

void DFS(int u) {
    dp[u][0] = 0;
    dp[u][1] = val[u];
    int siz = (int) head[u].size();
    for (int i = 0; i < siz; ++i) {
        int v = head[u][i];
        DFS(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += std::max(dp[v][0], dp[v][1]);
    }
}

int main() {
    IMPROVE_IO();
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    int maxNode = -1, minNode = MAXN + 1000;
    for (int i = 1; i <= n - 1; ++i) {
        int father = 0, child = 0;
        cin >> child >> father;
        head[father].push_back(child);
        ++inDegree[child];
        maxNode = std::max(maxNode, std::max(father, child));
        minNode = std::min(minNode, std::min(father, child));
    }
    int root = 0;
    for (int i = minNode; i <= maxNode; ++i) {
        if (inDegree[i] == false) root = i;
        if (root != 0) break;
    }
    DFS(root);
    cout << std::max(dp[root][0], dp[root][1]) << endl;
    return 0;
}