派对最大快乐值问题
派对最大快乐值问题
作者：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();
}
}
