N個の屋台をT時間の間に遊びたい。また、時刻Sの時に花火もみたい。
一つの屋台で遊ぶ時の楽しさと時間が与えられるので、楽しさを最大化しようという問題。なお、屋台は番号の若い順にしか回れず、一つの屋台では一度しか遊べない。
N個目までの屋台について、dp[時刻iまでで得られる楽しさの最大値]というDPを組む。
一つの屋台を複数回数えない工夫が必要だった。
計算量はO(N^2)
難易度は8程度に感じられた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2316399#1
