TopCoder SRM 679 div1 Easy: FiringEmployees

,

[FiringEmployees]()

解説

貪欲。葉の側から順に、解雇するかしないかを決めていけばよい。

実装

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
class FiringEmployees { public: int fire(vector<int> manager, vector<int> salary, vector<int> productivity); };

int FiringEmployees::fire(vector<int> manager, vector<int> salary, vector<int> productivity) {
    manager.insert(manager.begin(), -1);
    salary.insert(salary.begin(), 0);
    productivity.insert(productivity.begin(), 0);
    int n = manager.size();
    vector<vector<int> > subordinates(n);
    repeat_from (i,1,n) subordinates[manager[i]].push_back(i);
    vector<int> dp(n);
    repeat_reverse (i,n) {
        dp[i] = productivity[i] - salary[i]; // profit
        for (int j : subordinates[i]) {
            dp[i] += dp[j];
        }
        if (dp[i] < 0) dp[i] = 0; // fire
    }
    return dp[0];
}