派对的最大快乐值

公司员工可以用树形结构表示，除了老板以外，每个员工都有直属上级，除基层员工外，每个员工都有一个或者多个下级。公司要办party，请返回派对的最大快乐值。

某个员工来了，那他的直接下级不能参加。
派对快乐值是到场的所有员工快乐值的累加。
目标是让派对快乐值最大。

假设有头节点X，假设X的下级员工为A，B，C。，那么分为两种情况： 1. X不参加派对，那么快乐值为 NO_X和max(YES_C, NO_C)、max(YES_C, NO_C)、max(YES_C, NO_C)。 2. X参加派对，那么快乐值为YES_X和NO_A、NO_B、NO_C的快乐值的和。

显然是个递归结构，并且递归的过程需要返回node的YES_node值和NO_node值。（YES_node表示node参加，NO_node表示node不参加）。

use std::{cell::RefCell, rc::Rc};
struct Employ {
    happy: i32, // 快乐值
    subordinates: Vec<EmployRef>, // 下级员工
}

type EmployRef = Rc<RefCell<Employ>>;

impl Employ {
    fn new(happy: i32) -> Rc<RefCell<Employ>> {
        Rc::new(RefCell::new(Employ { happy, subordinates: vec![] }))
    }
    fn get_happy(&self) -> i32 {
        self.happy
    }

    fn add_subordinates<I>(&mut self, subordinates: I)
    where
        I: IntoIterator<Item = EmployRef>,
    {
        for subordinate in subordinates {
            self.subordinates.push(subordinate);
        }
    }

    fn get_subordinates(&self) -> &Vec<EmployRef> {
        &self.subordinates
    }
}

struct ReturnData {
    yes_head_max: i32,
    no_head_max: i32,
}

fn get_max_happy(employ: EmployRef) -> ReturnData {
    let mut yes = employ.borrow().get_happy();
    let mut no = 0;

    if employ.borrow().get_subordinates().is_empty() {
        return ReturnData {
            yes_head_max: yes,
            no_head_max: no,
        };
    } else {
        for sub in employ.borrow().get_subordinates() {
            let data = get_max_happy(sub.clone());
            yes += data.no_head_max;
            no += data.yes_head_max.max(data.no_head_max);
        }

        return ReturnData {
            yes_head_max: yes,
            no_head_max: no,
        };
    }
}

fn max_happy(employ: EmployRef) -> i32 {
    let data = get_max_happy(employ);
    return data.yes_head_max.max(data.no_head_max);
}

#[test]
fn test() {
    let employ = Employ::new(10);
    let employ1 = Employ::new(20);
    let employ2 = Employ::new(30);
    let employ3 = Employ::new(40);

    let employ_1_1 = Employ::new(50);
    let employ_1_2 = Employ::new(60);

    employ.borrow_mut().add_subordinates(vec![employ1.clone(), employ2.clone(), employ3.clone()]);
    employ1.borrow_mut().add_subordinates(vec![employ_1_1.clone(), employ_1_2.clone()]);

    assert_eq!(max_happy(employ), 180);
}

派对的最大快乐值

评论