派对的最大快乐值

[编程题]派对的最大快乐值

热度指数：4044 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。

这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：

1.如果某个员工来了，那么这个员工的所有直接下级都不能来。

2.派对的整体快乐值是所有到场员工快乐值的累加。

3.你的目标是让派对的整体快乐值尽量大。

给定一棵多叉树，请输出派对的最大快乐值。

输入描述:

第一行两个整数 n 和 root，n 表示公司的总人数，root 表示公司的老板。

第二行 n 个整数 happy_i 表示员工 i 的快乐值。

接下来 n - 1 行每行两个整数 u_i 和 v_i 表示 u_i 是 v_i 的直接上级。

输出描述:

输出一个整数表示最大快乐值。

示例1

输入

输出

备注:


输入保证是一棵树

算法知识视频讲解

Java

牛客241646630号

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static class TreeNode{
        //int index;
        int val;
        ArrayList<TreeNode> subordinates;

        public TreeNode(int val){
            //this.index = index;
            this.val = val;
            subordinates = new ArrayList<>();
        }
    }

    public class Info{
        int attend;
        int notAttend;

        public Info(int attend, int notAttend) {
            this.attend = attend;
            this.notAttend = notAttend;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int rootIndex = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n+1];
        for(int i = 1; i < n + 1; i++){
            nodes[i] = new TreeNode(sc.nextInt());
        }
        for(int j = 0; j < n-1; j++){
            nodes[sc.nextInt()].subordinates.add(nodes[sc.nextInt()]);
        }
        Main main = new Main();

        System.out.println(main.maxHappiness(nodes[rootIndex]));

    }

    public int maxHappiness(TreeNode root){
        Info r = recur(root);
        return Math.max(r.attend, r.notAttend);
    }

    public Info recur(TreeNode root){
        // 如果已经到达基层员工
        if(root.subordinates.isEmpty()) {
            return new Info(root.val, 0);
        }

        int attend = root.val;
        int notAttend = 0;

        for(TreeNode s: root.subordinates){
            Info i = recur(s);
            attend += i.notAttend;
            notAttend += Math.max(i.attend, i.notAttend);
        }
        return new Info(attend, notAttend);

    }
}

发表于 2022-03-26 16:55:56 回复(0)

Java

pein531

树型DP，建立多叉树，然后父节点分为来与不来两种情况往子节点要信息（子节点来时的最大快乐值，子节点不来时的最大快乐值），然后构成自己的信息返回给上一级使用。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.Iterator;

class Employee {
    public int happy;
    public LinkedList<Employee> subordinates;
    public Employee(int happy) {
        this.happy = happy;
        subordinates = new LinkedList<>();
    }
}

class Info {
    public int come;         // 来产生的快乐值
    public int notCome;      // 不来产生的快乐值
    public Info(int come, int notCome){
        this.come = come;
        this.notCome = notCome;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), bossId = Integer.parseInt(params[1]);
        int[] happy = new int[n];
        params = br.readLine().split(" ");
        for(int i = 0; i < n; i++) happy[i] = Integer.parseInt(params[i]);
        // 哈希表构建多叉树
        HashMap<Integer, Employee> map = new HashMap<>();
        Employee boss = new Employee(happy[bossId - 1]);
        map.put(bossId, boss);
        String line;
        while((line = br.readLine()) != null){
            params = line.split(" ");
            int idb = Integer.parseInt(params[0]), ids = Integer.parseInt(params[1]);
            Employee p = map.get(idb), c = new Employee(happy[ids - 1]);
            p.subordinates.add(c);
            map.put(ids, c);
        }
        // 树型DP
        Info info = process(boss);
        System.out.println(Math.max(info.notCome, info.come));
    }
    
    private static Info process(Employee e) {
        if(e.subordinates.isEmpty()) return new Info(e.happy, 0);
        int comeHappy = e.happy, notComeHappy = 0;
        Iterator<Employee> iter = e.subordinates.iterator();
        while(iter.hasNext()){
            Info info = process(iter.next());
            comeHappy += info.notCome;      // 如果我来，那我的部下就不能来
            notComeHappy += Math.max(info.come, info.notCome);      // 如果我不来，我的部下来不来都行，取大的那个
        }
        return new Info(comeHappy, notComeHappy);
    }
}

发表于 2021-11-18 16:48:46 回复(0)