公司聚会

题目

公司A有n个员工，数组happy表示n个员工产生快乐的分数，二维数组children表示公司的组织架构，children[i,j]=1代表i是j的直属上司。人事部门要举行一个聚会，为使聚会有愉悦的气氛，员工和其直属上司不会同时参加。请问怎么安排聚会名单，使聚会的快乐分数总和最大。
输入:
happy=[3,7,1,4,6,8,9,10,5,4,2,12,3,6]
children=
[[0,1,1,1,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]
输出：
54

思路

定义dp[i]表示以第i个顶点为根的树，其最大的快乐分数。因为有员工和直属上司不能同时参加的限制，所以分两种情况：树根参加或不参加。树根参加，则树根的直接子孩子不参加，而树根的孙子参加。树根不参加，所有孩子参加。比较这两种情况，较大者为dp[i]的值。

代码

#include <vector>
using namespace std;
class CompanyParty {
    vector<int> dp;
public:
    int settleCompanyParty(vector<int> happy, vector<vector<int>> children) {
        dp.resize(happy.size());
        getSum(0, happy, children);
        return dp[0];
    }
    void getSum(int node, vector<int> happy, vector<vector<int>> children) {
        //看node是不是叶子结点，如果是，则
        bool isleaf = true;
        for(int i = 0;i < children.size();i++) {
            if (children[node][i] == 1) {
                getSum(i, happy, children);
                isleaf = false;
            }
        }
        
        if (isleaf) {
            dp[node] = happy[node];
        }
        else {
            int sum1 = 0;//node不参加
            int sum2 = happy[node];//node参加
            for(int i = 0;i < children.size();i++) {
                if (children[node][i] == 1) {
                    sum1 += dp[i];
                    for(int j = 0;j < children.size();j++) {
                        if (children[i][j] == 1) {
                            sum2 += dp[j];
                        }
                    }
                }
            }
            if (sum1 > sum2) {
                dp[node] = sum1;
            }
            else {
                dp[node] = sum2;
            }
        }
    }
};