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); } };