hotpepsiの練習帳

SRM 679

02:12

https://competitiveprogramming.info/topcoder/srm/round/16649/div/1

Div1 Easy (250) FiringEmployees

問題

• 社長とN人の社員がいる
• それぞれのボス、給与、生産力が与えられる
• 生産力から給与をひいたものが利益となる
• 任意の社員を解雇できる
• ただし部下がいる社員を解雇すると部下も解雇する必要がある
• 利益の最大値を求める

方針

• 部下を含めたコストを計算しておく
• 先頭から足すかどうか貪欲に決める
• Passed System Test
• (解き直し)
• 後方には部下しかいない(上司がいない)ので、末尾から貪欲に足すことができる
• 自分iのコストをa[i]とする
• 自分の利益をdとして、a[i]に足す
• a[i]がプラスであれば、a[boss]にa[i]を足すことで、a[i]が再帰的に計算できる
• a[0]が答え
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_679/FiringEmployees.cpp

結果

o-- 151.54pt 345th/454 rating 1407 -> 1365 (-42)

珍しくeasyが簡単な回。

http://togetter.com/li/928104