夜店(12本選3)

N個の屋台をT時間の間に遊びたい。また、時刻Sの時に花火もみたい。

一つの屋台で遊ぶ時の楽しさと時間が与えられるので、楽しさを最大化しようという問題。なお、屋台は番号の若い順にしか回れず、一つの屋台では一度しか遊べない。

N個目までの屋台について、dp[時刻iまでで得られる楽しさの最大値]というDPを組む。

一つの屋台を複数回数えない工夫が必要だった。

計算量はO(N^2)

難易度は8程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2316399#1