• 数据库
  • Mysql
  • Nosql
  • 技术框架
  • Spring
  • Kafka
  • ibatis
  • 分布式
  • Linux
  • 关于我们
  • 注册
  • 登录
  • 欧宝安德拉-多叉树-组织party最大快乐值

    2022-5-7 diaba 欧宝安德拉

    package com.jiucaiyuan.net.algrithm.tree;
    
    import java.util.List;
    
    /**
     * <pre>
     * 树形dp套路
     * 树形dp套路使用前提:
     * 如果题目求解目标是S规则,则求解流程可以定成每一个节点为头节点的子树
     * 在S规则下的每个答案,并且最终答案一定在其中
     * 案例题
     * 【题目】派对的最大快乐值
     * 员工信息定义如下
     * class Employee{
     * public int happy; //这名员工带来的快乐值
     * List<Employee> subordinates; //这名员工有哪些直接下级
     * }
     * 公司每名员工都符合Employee类的描述,整个公司的人员结构可以看做是
     * 标准的、没有环的多叉树,树的头结点可以看做是公司唯一的老板,除了老板
     * 外,每个员工都有唯一的上级。叶子结点是没有直接下级的基层员工(subordinates
     * 列表为null),除了基层员工外,每个员工都有一个或多个直接下级。
     * 这个公司要办party,你可以决定哪些员工来,哪些员工不来,但是要遵循
     * 如下规则:
     * 1.如果某个员工来了,那么这个员工的直接下级都不能来;
     * 2.派对的整体快乐值是到场的所有员工快乐值的累加;
     * 3.你的目标是让派对的整体快乐值最大;
     * 给定一个多叉树的头结点boss,请返回派对的最大快乐值
     * 【思路】
     * 划分为几种情况:
     * 1.头结点参与,最大快乐值=直属员工不参与的情况下最大快乐值的累加和;
     * 2.头结点不参与,轮训所有直属员工,直属员工来的情况下最大快乐值的累加和+直属员工不来的情况下最大快乐累加值;
     * 从两种中累加,就是整party最大的快乐值
     * 子树返回的结果:头结点来时的最大快乐值,头结点不来时的最大快乐值
     * </pre>
     *
     * @Author jiucaiyuan  2022/5/6 23:06
     * @mail services@jiucaiyuan.net
     */
    
    public class MaxHappyValue {
        public static class Employee {
            public int happy;
            public List<Employee> subordinates;
        }
    
        public static class Info {
            public int yesMaxHappy;  //来的时候最大快乐值
            public int noMaxHappy;   //不来时最大快乐值
    
            public Info(int yes, int no) {
                this.yesMaxHappy = yes;
                this.noMaxHappy = no;
            }
        }
    
        /**
         * 取得以boss为老板的公司组织party获得的最大快乐值
         *
         * @param boss 整个公司唯一的老板
         * @return 最大快乐值
         */
        public static int maxHappy(Employee boss) {
            Info info = process(boss);
            return Math.max(info.yesMaxHappy, info.noMaxHappy);
        }
    
        /**
         * @param employee 当前员工来与不来获得的最大快乐值
         * @return
         */
        private static Info process(Employee employee) {
            if (employee == null) {
                return new Info(employee.happy, 0);
            }
            //当前员工来,再统计直属下级不来时最大快乐值累加
            int yes = employee.happy;
            //当前员工不来,再统计直属下级来与不来时最大快乐值累加
            int no = 0;
            for (Employee e : employee.subordinates) {
                Info eInfo = process(e);
                //当前员工来,直接下属不来时的快乐值
                yes += eInfo.noMaxHappy;
                //当前员工不来,下属可以来也可以不来,得到最大快乐值
                no += Math.max(eInfo.yesMaxHappy, eInfo.noMaxHappy);
            }
            return new Info(yes, no);
        }
    }
    

    发表评论:

  • 最新文章

  • Go-数组,切片,map
  • scp拷贝文件
  • 笔试题-牛羊吃草问题
  • 笔试题-最少的袋子数装苹果
  • 递归DP-找零钱的方法数
  • 存档

  • 2022年10月(1)
  • 2022年8月(1)
  • 2022年6月(11)
  • 2022年5月(6)
  • 2022年4月(33)
  • 2022年3月(26)
  • 2021年3月(1)
  • 2020年9月(2)
  • 2018年8月(1)
  • 2018年3月(1)
  • 2017年3月(3)
  • 2017年2月(6)
  • 2016年12月(3)
  • 2016年11月(2)
  • 2016年10月(1)
  • 2016年9月(3)
  • 2016年8月(4)
  • 2016年7月(3)
  • 2016年6月(4)
  • 2016年5月(7)
  • 2016年4月(9)
  • 2016年3月(4)
  • 2016年2月(5)
  • 2016年1月(17)
  • 2015年12月(15)
  • 2015年11月(12)
  • 2015年10月(6)
  • 2015年9月(11)
  • 2015年8月(8)
  • 分类

  • Java(4)
  • 基础(8)
  • IO(3)
  • JVM(7)
  • 多线程(11)
  • 调优命令(1)
  • Go(0)
  • 基础(1)
  • Linux(10)
  • mac(12)
  • 数据库(2)
  • Mysql(7)
  • Nosql(8)
  • 技术框架(2)
  • Spring(5)
  • Kafka(3)
  • ibatis(2)
  • 分布式(4)
  • 数据结构与欧宝安德拉(0)
  • 数据结构(6)
  • 欧宝安德拉(44)
  • 笔试题(19)
  • emlog(1)
  • 问题解决记录(2)
  • 随笔记录(26)
  • 金融(1)
  • 工具使用(8)
  • 操作系统(3)
  • 用友NC(3)
  • NC常见问题(2)
  • 热门文章

  • SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
  • Mac-删除卸载GlobalProtect
  • java.lang.SecurityException: JCE cannot authenticate the provider BC
  • Idea之支持lombok编译
  • MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
  • 标签

    mac emlog NC授权 授权数 用户数 破解 天上一天 redis 已达授权数 用友NC 可打印 地上一年 超光速 大于光速 时间静止 时光倒流 相对论 go基础 shell CountDownLatch 狱中诗 线程同步 任务同步 SecureCRT 光标消失 做人 做事 职业发展 选人 转义字符 json 格式错误 内存分区 操作系统 cache 分布式 程序 Linux crontab 定时任务 license 安全 备份 IO操作 同步 异步 阻塞 进程 线程 并发 共享内存 mybatis Improper inline 数据库 mysql 如果为null query paxos 分布式一致性 if ifnull spring ioc BlockingQueue OOM 软引用 弱引用 并行 jvm参数 gc jvm kafka 2016 数据库引擎 加密 解密 java文件压缩 命令 RDB AOF 配置 调优 sharding jvm结构 存储引擎 myiasm innodb 乐观锁 悲观锁 理财 欧宝安德拉 异地多活 ctrl+alt+delete idea lombok springmvc aes 宝宝 项目经理 nc curl 按位操作 逻辑思维 excel 原子增操作 awk printf OceanBase mac锁屏 快捷键 文件监听 confict git 商品管理 sku 自动注入 Apple ID Javassist branch 正则表达式 参数必填 代码优化 grep 程序员 未来 保险 坦然生活 抗风险 优秀经纪人 汉诺塔 递归
  • 最新评论

  • logisqykyk
    Javassist分析、编辑和创建jav...
  • xxedgtb
    Redis—常见参数配置 - 韭菜园 ...
  • wdgpjxydo
    SpringMVC:Null Model...
  • rllzzwocp
    Mysql存储引擎MyISAM和Inno...
  • dpkgmbfjh
    SpringMVC:Null Model...
  • tzklbzpj
    SpringMVC:Null Model...
  • bqwrhszmo
    MyBatis-Improper inl...
  • 乐谱吧
    good非常好
  • diaba
    @diaba:应该说是“时间的度量依据”...
  • diaba
    如果速度增加接近光速、等于光速、甚至大于...
  • 最新微语

  • 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界

    2022-03-21 23:31

  • 2022.03.02 23:37:59

    2022-03-02 23:38

  • 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!

    2018-07-18 10:49

  • 2018年关键字“走心”

    2018-03-19 16:07

  • 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!

    2017-12-20 10:24

  • 更多»

    Powered by emlog 京ICP备15045175号-1 Copyright © 2022