POJ 1949. Chores

問題

仕事がN個ある。しかし、K番目の仕事は、1〜K-1番目の仕事に0個以上依存しており、前の仕事がすべて終わっていないと手を付けられない。
各仕事にかかる時間とK番目の仕事が依存している仕事番号のリストが与えられるので、すべての仕事が終わるまでにかかる最小時間を答える。

3<=N<=10^5
1<=各仕事にかかる時間<=100

考え方

K番目の仕事は依存する仕事のうち、一番時間がかかっている仕事が終わるまで待たなければならない。
これは簡単なDPで、dp[i]:=仕事iが終わる最短時間とすると、
・依存している仕事がなければ、その仕事単体の時間
・依存している仕事があれば、dp[依存している仕事で一番遅くに終わるもの]＋その仕事単体の時間
で求められる。
最後に、dp[i]で一番遅いものを答えればよい。

ちなみに、c++でcout/cin使うとTLE。(ios::sync_with_stdio(false);を追加とかで対処)