You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

5.2 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 285. 没有上司的舞会

一、题目描述

Ural 大学有 N 名职员,编号为 1N他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 H_i 给出,其中 1≤i≤N

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值

输入格式

第一行一个整数 N

接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi

接下来 N1 行,每行输入一对整数 L,K,表示 KL 的直接上司。

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

输入样例

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

输出样例

5

二、理解与分析

  • 看完题,知道这是一道与树相关的试题

  • 对于某个人来讲,他是否参加都是可以的,但他是否参加直接影响着他下属的选择

    • 他参加,那么,他的直接下属不来了,下属的下属不受此影响
    • 他不参加,那么,他的直接下属还是有两种选择,参加或不参加
  • 分析到这里,似乎这和最初的01背包是多么的相像,可以选时,有可能选择,可能放弃;不能选时,直接放弃,这不就是dp吗?

  • 因为上面提到了是一道与树相关的试题,在树上dp,躲不开dfs

  • 如果是dp的话,需要设计一下状态的计算结果数组,有人管它叫做 状态表示。那怎么表示呢?dp的话,强调的是状态转移要方便快捷,第一个维度肯定是子树的根节点,比如f[u]

  • 如果只有一维就可以的话,就不用考虑增加维度了。我们来思考一下一维是否够用:一个小领导A,他要关心自己下属子树的Happy值最大,他面临两种选择

    • 自己参加舞会
    • 自己不参加舞会
  • 这两种选择,使得后继的员工选择会发生变化,导致整体的Happy值变化。A需要思考两种情况,拿到两种情况的最大值后,进行一次max运算,才是答案。

  • 这两种情况,可以视为两条路,分别是在A参加和不参加情况下。

  • 这两条路径,递推的结果汇总是不一样的,所以增加二维,变成f[u][0],f[u][1],分别

    • 表示以u为根的子树,并且,不选择u的情况
    • 表示以u为根的子树,并且,选择u的情况
  • 上面都想明白后,再考虑一些细节

    • 如何建树呢?谁向谁建边呢?树一般就是树向分枝建边,也就是 一对多正确,多对一错误
    • dfs需要从哪个节点开始进行搜索呢?一般是根,本题没有告诉我们几号员工是大老板,我们还需要根据入度出度的关系来决策谁是大老板。

三、动态规划分析

状态表示

f[u][1]表示以u为根节点的子树并且包括u的总快乐指数

f[u][0]表示以u为根节点并且不包括u的总快乐指数

状态计算 要想求得一棵以u为根节点的子树的最大指数分为两种:选u节点或不选u节点

记点u的子节点是j

  • 1.选u\large f[u][1]=\sum f[v][0]
  • 2.不选u\large f[u][0]=\sum max(f[v][1],f[v][0])

记根节点为rootroot开始dfs一遍即可 最后输出max(f[root][1],f[root][0])

可以参阅它的姊妹题 AcWing 323 . 战略游戏

四、实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 6010;

int happy[N]; // 快乐值
int in[N];    // 入度
int f[N][2];  // dp的状态结果数组
int n;

// 构建邻接表
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 通过深度优先搜索,对树进行遍历
void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        dfs(v);                           // 继续探索它的孩子,它的值是由它的孩子来决定的
        f[u][1] += f[v][0];               // 它选择了,它的孩子就不能再选
        f[u][0] += max(f[v][0], f[v][1]); // 它不选择,那么它的每一个孩子,都是可以选择或者不选择的
    }
    // 不管是不是叶子结点都会产生happy[u]的价值
    f[u][1] += happy[u];
}

int main() {
    // 邻接表表头初始化
    memset(h, -1, sizeof h);

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

    // 读入树
    for (int i = 1; i < n; i++) { // n-1条边
        int x, y;
        cin >> x >> y;
        add(y, x);
        in[x]++; // 记录入度因为需要找出大boss
    }

    // 从1开始找根结点
    int root = 1;
    while (in[root]) root++; // 找到根结点,入度为0

    // 递归
    dfs(root);

    // 取两个
    printf("%d\n", max(f[root][0], f[root][1]));

    return 0;
}