派对最大快乐值问题
作者：Grey
原文地址：
题目描述
员工信息的定义如下:
public static class Employee { public int happy; // 这名员工可以带来的快乐值 public List<Employee> 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){} 表示当前员工来或者不来的最大快乐值是多少。
接下来是整理可能性
-
当前员工参加，下属员工都不可以参加
-
当前员工不参加，下属员工可以参加也可以不参加
依据上述可能性，递归函数实现如下（核心代码见注释说明）
public static Info p(Employee boss) { if (boss.subordinates == null || boss.subordinates.isEmpty()) { return new Info(boss.happy, 0); } List<Employee> 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<Employee> 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<Employee> 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<Integer, Employee> map = new HashMap<>(); List<Integer> tmp = new LinkedList<>(); for (int i = 1; i <= count; i++) { int happy = sc.nextInt(); map.put(i, new Employee(happy)); tmp.add(i); } Set<Integer> 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(); } } 
