今年初SRM。Easy早解き+1Chalしたけどレート微減だった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14122
問題
社員番号0~Nの(N+1)人の会社がある。
0番の社員は社長である。
それ以外の社員はそれぞれ1人自分より若い番号M[i]の人をボスとする。
そのためボスと部下の関係は社長を根とした木を成す。
各社員の給料はS[i]であり、売上はP[i]である。
よって社員を雇う利益(損失)はP[i]-S[i]である。
各社員は任意に解雇することができる。
ただし解雇するとその部下もすべて連鎖的に解雇することになる。
残った社員の利益の総和を最大化せよ。
解法
各人の利益をC[i]=P[i]-S[i]とする。
葉から順に、「自分のSubTreeの利益の総和が負なら、自分以下を切る。そうでなければSubTreeの総和を親に加算する」という処理を行い、社長の総利益を答えればよい。
class FiringEmployees { public: int fire(vector <int> M, vector <int> S, vector <int> P) { int C[3050]={}; for(int i=M.size();i>0;i--) C[M[i-1]]+=max(0,P[i-1]-S[i-1]+C[i]); return C[0]; } }
まとめ
一見O(N^2)っぽい制限だけどそんなことはなかった。