WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM679 Div1 Easy "FiringEmployees"

解法

dfsして貪欲に。
自分を含めてマイナスになったら自ら首を切って0を返して会社に貢献しよう。(部下を道連れに)

ソースコード

vector<int> G[2550];
int P[2550];

class FiringEmployees {
    public:
    int fire(vector<int> m, vector<int> s, vector<int> p) {
        int n = m.size();

        for (int i = 0; i <= n; i++) {
            G[i].clear();
        }

        P[0] = 0;
        for (int i = 1; i <= n; i++) {
            G[m[i - 1]].push_back(i);
            P[i] = p[i - 1] - s[i - 1];
        }

        return solve(0);
    }

    int solve(int cur) {
        int res = 0;
        for (int i = 0; i < G[cur].size(); i++) {
            int t = solve(G[cur][i]);
            if (t >= 0) {
                res += t;
            }
        }
        res += P[cur];
        return max(res, 0);
    }
};