SRM619Div1Medium

問題

N人の社員とK個の仕事と仕事を覚えるのに必要なコストが与えられる。社員の構成はピラミッド状になっており、0番目の社員以外は必ず上司がいる。
直属の部下と上司の固まりを部署とする。各社員は必ず2つの違う仕事を習得している。同じ部署内で全員が違う仕事を習得している時の最小のコストを求めよ。

解法

習得のコストを昇順に並べて、貪欲法で解を求めることができそうだが、上司の習得しだいでは最適化にならない。
dp[x][p]:=最小コストとし動的計画法で解いていく。xは上司の番号、pは上司の習得スキルである。部署内でのコストは最小費用流で求められる。
全体の計算量はN=Kとすると、 $O(N^6)$ になるがならし計算量で多く見積もっているので通すことができる。