SRM 679 div1 easy: FiringEmployees
SRM 679 に参加しました。easy がめっちゃ簡単だったんですが英弱パワーを発揮して点数が低かったです。
問題
木構造になっている社員関係が与えられる。各社員 v は, productivity[v] - salary[v] だけの利益を挙げられる。
利益を最大化するために社員を首にすることを考えているが, 社員 v を首にした場合, v の以下の子はすべて首にしなければならない。この場合に利益は最大でいくらになるか。
解法
木 dp やるだけ。
vi G[3000]; vector<int> salary, productivity; int dfs(int v, int p) { int ret = 0; if (v == 0) { for (int ch : G[v]) { ret += dfs(ch, v); } return ret; } int tmp = productivity[v-1] - salary[v-1]; for (int ch : G[v]) { if (ch == p) continue; tmp += dfs(ch, v); } ret = max(ret, tmp); return ret; } class FiringEmployees { public: int fire(vector <int> manager, vector <int> sala, vector <int> product) { int n = manager.size(); salary = sala; productivity = product; for (int i = 0; i <= n; i++) G[i].clear(); for (int i = 1; i <= n; i++) { G[manager[i-1]].push_back(i); G[i].push_back(manager[i-1]); } return dfs(0, -1); } };