侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【树形DP】没有上司的舞会

GabrielxD
2022-11-30 / 0 评论 / 0 点赞 / 459 阅读 / 1,128 字
温馨提示:
本文最后更新于 2022-12-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

285. 没有上司的舞会


Ural 大学有 NN 名职员,编号为 1N1 \sim N

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 HiH_i 给出,其中 1iN1 \le i \le N

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

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

输入格式

第一行一个整数 NN

接下来 NN 行,第 ii 行表示 ii 号职员的快乐指数 HiH_i

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

输出格式

输出最大的快乐指数。

数据范围

1N60001 \le N \le 6000 ,
128Hi127-128 \le H_i \le 127

输入样例:

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

输出样例:

5

解题

方法一:动态规划

思路

抽象地理解一下题意:在一棵树中,每个节点都有其权值,在选出的节点不存在边的情况下,选出节点,并使选出节点的权值累和最大,求这个最大的累和权值。

在树中每个节点只与其父节点与子节点相连,从叶节点向根节点考虑时:

  • 若选择该节点,那么其每个子节点都不能选,求累和。
  • 若不选给节点,那么对每个子节点求选/不选的最大值,求累和。

思维过程:

image-20221130215014466

动态规划:

  • 状态定义:

    • dp[u][0]dp[u][0] 表示所有从以点 uu 为根节点的子树中选择,且不选uu 的方案的最大的快乐指数。
    • dp[u][1]dp[u][1] 表示所有从以点 uu 为根节点的子树中选择,且选择uu 的方案的最大的快乐指数。
  • 状态转移方程:(vvuu 的子节点)

    • dp[u][0]=max(dp[v][0],dp[v][1])dp[u][0] = \sum {\max(dp[v][0], dp[v][1]})
    • dp[u][1]=dp[v][0]dp[u][1] = \sum {dp[v][0]}
  • 初始状态:第一次状态转移前,对于所有节点,选择自己时子树的快乐指数和为它自己的快乐指数,即:dp[u][1]=happy[u]dp[u][1] = happy[u]

代码

import java.util.*;
import java.io.*;

public class Main {
    static int[] heads, happy, vals, nexts; // 邻接表存图
    static int n, idx;
    static boolean[] hasBoss;
    static int[][] dp;
    
    static void add(int a, int b) {
        vals[idx] = b;
        nexts[idx] = heads[a];
        heads[a] = idx++;
    }
    
    static void dfs(int u) {
        dp[u][1] = happy[u];
        for (int i = heads[u]; i != -1; i = nexts[i]) {
            int v = vals[i];
            dfs(v);
            dp[u][0] += Math.max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        heads = new int[n + 1];
        Arrays.fill(heads, -1);
        happy = new int[n + 1];
        vals = new int[n];
        nexts = new int[n];
        hasBoss = new boolean[n + 1];
        dp = new int[n + 1][2];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            happy[i] = (int) in.nval;
        }
        for (int i = 1; i < n; ++i) {
            in.nextToken();
            int k = (int) in.nval;
            in.nextToken();
            int l = (int) in.nval;
            add(l, k);
            hasBoss[k] = true;
        }
        int root = 1;
        while (hasBoss[root]) ++root; // 找根节点
        dfs(root);
        System.out.println(Math.max(dp[root][0], dp[root][1]));
    }
}
#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;
int heads[N], happy[N], vals[N], nexts[N];
int n, idx;
int dp[N][2];
bool has_boss[N];

void add(int a, int b) {
    vals[idx] = b;
    nexts[idx] = heads[a];
    heads[a] = idx++;
}

void dfs(int u) {
    dp[u][1] = happy[u];
    for (int i = heads[u]; ~i; i = nexts[i]) {
        int v = vals[i];
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    memset(heads, -1, sizeof(heads));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &happy[i]);
    for (int i = 1; i < n; ++i) {
        int l, k;
        scanf("%d%d", &l, &k);
        add(k, l);
        has_boss[l] = true;
    }
    int root = 1;
    while (has_boss[root]) ++root;
    dfs(root);
    printf("%d\n", max(dp[root][0], dp[root][1]));
    
    return 0;
}
0

评论区