• 派对最大快乐值问题


    派对最大快乐值问题

    作者:Grey

    原文地址:

    博客园:派对最大快乐值问题

    CSDN:派对最大快乐值问题

    题目描述

    员工信息的定义如下:

        public static class Employee {
            public int happy; // 这名员工可以带来的快乐值
            public List subordinates; // 这名员工有哪些直接下级
    
            public Employee(int h) {
                happy = h;
                subordinates = new ArrayList<>();
            }
        }
    

    公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。

    叶节点是没有任何下属的基层员工(subordinates列表为空),除基层员工外,每个员工都有一个或多个直接下级。这个公司现在要办 party,你可以决定哪些员工来,哪些员工不来,

    规则:

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

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

    3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点 boss,请返回派对的最大快乐值。

    题目链接: 没有上司的舞会

    本题可以用二叉树的递归套路方法来解,

    定义如下数据结构

        public static class Info {
            public int yes;
            public int no;
     
            public Info(int yes, int no) {
                this.yes = yes;
                this.no = no;
            }
        }
    

    其中:

    yes变量表示当前员工来的话,最大快乐值是多少。

    no变量表示当前不来的话,最大快乐值是多少。

    定义递归函数

    public static Info p(Employee boss){}
    

    表示当前员工来或者不来的最大快乐值是多少。

    接下来是整理可能性

    1. 当前员工参加,下属员工都不可以参加

    2. 当前员工不参加,下属员工可以参加也可以不参加

    依据上述可能性,递归函数实现如下(核心代码见注释说明)

        public static Info p(Employee boss) {
            if (boss.subordinates == null || boss.subordinates.isEmpty()) {
                return new Info(boss.happy, 0);
            }
            List subordinates = boss.subordinates;
            int yes = boss.happy;
            int no = 0;
            for (Employee e : subordinates) {
                Info info = p(e);
                // boss参加了,下属可以不参加
                yes += info.no;
                // boss没有参加,下属可以参加也可以不参加
                no += Math.max(info.yes, info.no);
            }
            return new Info(yes, no);
        }
    

    主函数直接调用

    Info info = p(boss);
    // 当前员工来或者不来的最大值
    return Math.max(info.yes, info.no);
    

    完整代码见

    import java.util.*;
     
    public class Main {
        public static class Employee {
            public int happy;
            public List subordinates;
     
            public Employee(int happy) {
                this.happy = happy;
                this.subordinates = new ArrayList<>();
            }
        }
     
     
        public static class Info {
            public int yes;
            public int no;
     
            public Info(int yes, int no) {
                this.yes = yes;
                this.no = no;
            }
        }
     
        public static int maxHappy(Employee boss) {
            if (boss == null) {
                return 0;
            }
            Info info = p(boss);
            return Math.max(info.yes, info.no);
        }
     
        public static Info p(Employee boss) {
            if (boss.subordinates == null || boss.subordinates.isEmpty()) {
                return new Info(boss.happy, 0);
            }
            List subordinates = boss.subordinates;
            int yes = boss.happy;
            int no = 0;
            for (Employee e : subordinates) {
                Info info = p(e);
                // boss参加了,下属可以不参加
                yes += info.no;
                // boss没有参加,下属可以参加也可以不参加
                no += Math.max(info.yes, info.no);
            }
            return new Info(yes, no);
        }
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int count = sc.nextInt();
            Map map = new HashMap<>();
            List tmp = new LinkedList<>();
            for (int i = 1; i <= count; i++) {
                int happy = sc.nextInt();
                map.put(i, new Employee(happy));
                tmp.add(i);
            }
            Set notBoss = new HashSet<>();
            for (int i = 1; i <= count; i++) {
                if (i != count) {
                    int child = sc.nextInt();
                    int father = sc.nextInt();
                    notBoss.add(child);
                    Employee f = map.get(father);
                    Employee c = map.get(child);
                    f.subordinates.add(c);
                }
            }
            int bossIndex = 0;
            for (Integer it : tmp) {
                if (!notBoss.contains(it)) {
                    bossIndex = it;
                    break;
                }
            }
            Employee boss = map.get(bossIndex);
            System.out.println(maxHappy(boss));
            sc.close();
        }
    }
    

    更多#

    算法和数据结构笔记

  • 相关阅读:
    智能制造中后期:深挖成本、提升效率的关键——标准工时
    wpf中TreeView的滚动条
    KT6368A距离_以及蓝牙的性能描述和远距离怎么办
    【Python Web】Flask框架(六)JavaScript基础
    【离散化 二维差分】391. 完美矩形
    Java实现JSON{参数}占位符名称替换指定的多个变量值
    哈夫曼编码原理
    实现精细化生产, MES、APS、ERP必不可少
    第八章 时序检查(中)
    [AUTOSAR][诊断管理][ECU][$14] 清除诊断相关信息
  • 原文地址:https://www.cnblogs.com/greyzeng/p/16748043.html