栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode笔记---树型DP

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode笔记---树型DP

285. 没有上司的舞会

Ural 大学有 N 名职员,编号为 1∼N。

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

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

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

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

输入格式 第一行一个整数 N。

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

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

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

数据范围 1≤N≤6000, −128≤Hi≤127
输入样例: 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5
输出样例: 5

(下面代码的dp[x][0] 代表的是该节点的参加,1是不参加)

import java.util.Scanner;
import java.util.*;

public class Main {
    
    static int[] h = new int[6001];
    
    static int[][] v = new int[6001][6001];
    
    static Scanner scan = new Scanner(System.in);
    
    static int[][] dp = new int[6001][2];
    
    public static void main(String[] args) {
        int N = Integer.valueOf(scan.nextLine());
        int t = N;
        for (int i = 0; i < N; i++) {
            h[i + 1] = Integer.valueOf(scan.nextLine());
        }
        for (int i = 0; i < N - 1; i++) {
            String[] split = scan.nextLine().split(" ");
            int l = Integer.valueOf(split[0]);
            int k = Integer.valueOf(split[1]);
            List son = v.getOrDefault(k, new ArrayList<>());
            son.add(l);
            v.put(k, son);
            v[k][]
        } 
        int p = findPar(N);
        dfs(p);
        System.out.println(Math.max(dp[p][1], dp[p][0]));
    }
    
    private static void dfs(int p) {
        dp[p][0] = h[p];
        dp[p][1] = 0;
        List son = v.get(p);
        if (son == null) {
            return;
        }
        for (Integer s: son) {
            dfs(s);
            dp[p][1] += Math.max(dp[s][0], dp[s][1]);
            dp[p][0] += dp[s][1];
        }
    }
    
    private static int findPar(int N) {
        int[] vis = new int[N + 1];
        for (Integer k: v.keySet()) {
            List son = v.get(k);
            for (Integer s: son) {
                vis[s] = 1;
            }
        }
        for (int i = 1; i <= N; i++) {
            if (vis[i] == 0) {
                return i;
            }
        }
        return 1;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959563.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号