没有上级的party
题目描述
员工信息的定义如下:
struct employee
{
int happy; // 这名员工可以带来的快乐值
list<employee*> inferior; // 这名员工有哪些直接下级
employee(int _happy):happy(_happy){}
};
公司的每个员工都符合 employee 结构体的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。
叶节点是没有任何下属的基层员工(inferior链表为空),除基层员工外,每个员工都有一个或多个直接下级。这个公司现在要办 party,你可以决定哪些员工来,哪些员工不来。
规则:
1.如果某个员工来了,那么这个员工的所有直接下级都不能来
2.派对的整体快乐值是所有到场员工快乐值的累加
3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点 boss,请返回派对的最大快乐值。
思路过程
- 一个员工只可能出现两种情况:来,或者不来。
- 一个员工不来有两种情况:上级来了,或者上级没来但自己不想来。
- 一个员工来,说明:上级没来,且自己想来。
- 统计一个员工来或者不来情况下的快乐值(包括对下级的影响),取其最大值。
现有公司层级如下图:
struct employee
{
int happy; // 这名员工可以带来的快乐值
list<employee*> inferior; // 这名员工有哪些直接下级
employee(int _happy):happy(_happy){}
};
int process(employee* superior, bool present)
{
int max = 0;
auto p = superior->inferior.begin();
while(p != superior->inferior.end())
{
if(present == true)//上级来了,则该员工不能来
max += process((*p), false);
else//上级没来,该员工可来可不来
{
int go = (*p)->happy + process((*p), true);
int notGo = process((*p), false);
max += std::max(go, notGo);
}
p++;
}
return max;
}
int happyVal(employee* root)
{
if(root == nullptr)
return 0;
int m = std::max(process(root, true), process(root, false));
return m;
}
测试:
int main()
{
// 4
// / | \
// 13 3 10
// /\\ /\\
// 1 3 8 5 3 1
// / \
// 5 4
employee* root = new employee(4);
root->inferior.push_back(new employee(13));
root->inferior.push_back(new employee(3));
root->inferior.push_back(new employee(10));
root->inferior.back()->inferior.push_back(new employee(5));
root->inferior.back()->inferior.push_back(new employee(3));
root->inferior.back()->inferior.push_back(new employee(1));
root->inferior.front()->inferior.push_back(new employee(1));
root->inferior.front()->inferior.push_back(new employee(3));
root->inferior.front()->inferior.push_back(new employee(8));
root->inferior.front()->inferior.back()->inferior.push_back(new employee(5));
root->inferior.front()->inferior.back()->inferior.push_back(new employee(4));
int val = happyVal(root);
std::cout << val;
}
版权声明:
本站所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
后端技术分享!
喜欢就支持一下吧