树形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

输出格式
输出最大的快乐指数。

题解

这可能是一道最简单的树形DP题目了。

我用的是邻接矩阵存树，$a[i][j]$代表$i$是$j$的上司。

我们设$f[i][j]$表示第$j$个人来不来参加舞会。$i$为true代表来参加，false代表不来参加。

对于每一个人，如果他的下属们来参加，便有：

他自己一定不能来，否则冲突，下属可以来也可以不来，所以有三种情况

$$f[1][j] = \max(f[1][j],f[1][j] + f[0][i],f[0][i])$$

若下属不来：

他的上司可以来也可以不来，所以也有三种情况

$$f[0][j] = \max(f[0][j], f[1][i] + f[0][j], f[1][i]);$$

我们找到树根，一遍DP就行。

#include <iostream>
#include <algorithm>
#define maxn 6005
using namespace std;

int n, v[maxn] = {}, x, y;
int a[maxn][maxn] = {};
int f[3][maxn] = {};
int root[maxn] = {};

void dfs(int x)
{
    for (register int i = 1; i <= n; i++)
        if (a[i][x])
        {
            dfs(i);
            f[0][x] = max(max(f[0][x], f[1][i] + f[0][x]), f[1][i]);
            f[1][x] = max(max(f[1][x], f[0][i] + f[1][x]), f[0][i]);
        }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (register int i = 1; i <= n; i++)
        cin >> f[1][i];

    for (register int i = 1; i < n; i++)
    {
        cin >> x >> y;
        root[x] = 1;
        a[x][y] = 1;
    }

    int r;
    for (register int i = 1; i <= n; i++)
        if (!root[i])
        {
            r = i;
            break;
        }
    dfs(r);

    cout << max(f[1][r], f[0][r]) << endl;

    return 0;
}