洛谷-P1352 没有上司的舞会（树型DP经典入门题）

题目描述

某大学有 $n$个职员，编号为 $1\ldots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 n*n*。

第 22 到第 (n + 1)(n+1) 行，每行一个整数，第 (i+1)(i+1) 行的整数表示 i*i* 号职员的快乐指数 r_i*r**i*。

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

输出格式

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

输入输出样例

输入 #1

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

输出 #1

5

说明/提示

数据规模与约定

对于 100\%100% 的数据，保证 1\leq n \leq 6 \times 10^31≤n≤6×103，-128 \leq r_i\leq 127−128≤r**i≤127，1 \leq l, k \leq n1≤l,k≤n，且给出的关系一定是一棵树。

---

分析：用d[i][0]表示当i不参加时的最大快乐指数和，状态转移方程： $$ d[i][0] = \sum_{s \in \text{son}(i)} \max (d[s][0], d[s][1]) $$ 上面方程的意思是，上司i选择不参加，那么i的直接下属可以选择参加，也可以选择不参加，应该选择两者中的最大值，最后对所有下属的快乐指数求和。

用d[i][1]表示上司i参加的最大快乐指数，设上司i个人的快乐指数是happiness[i]，如果上司i参加，那么它们的下属都不能参加，于是状态转移方程： $$ d[i][1] = \text{happiness}[i] + \sum_{s \in \text{son}(i)} d[s][0] $$ 那么最终的结果就是d[i][0], d[i][1]中的最大值了。因为只需要一次遍历，时间复杂度$O(n)$，空间复杂度$O(n)$。

//洛谷-P1352 没有上司的舞会
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> happiness(6005);
vector<vector<int>> d(6005, vector<int>(2)), son(6005);
vector<bool> haveParent(6005, false);


void solve(int start)
{
    d[start][1] = happiness[start];
    for (const auto & e : son[start]) {
        solve(e);
        d[start][0] += max(d[e][0], d[e][1]);
        d[start][1] += d[e][0];
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> happiness[i];
    int employee, boss;
    for (int i = 1; i < n; ++i) {
        cin >> employee >> boss;
        haveParent[employee] = true;
        son[boss].push_back(employee);
    }

    int start = 0;
    for (int i = 1; i <= n; ++i) {
        if (!haveParent[i]) { start = i; break; }
    }

    solve(start);
    cout << max(d[start][0], d[start][1]) << endl;

    return 0;
}

另外上面的代码使用了C++11新标准的auto，在POJ里是不能使用的，注意改写。