Roller Coaster (UVa Live Archive North America - Southeast - 2010/2011)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4870

問題

区間がN個あるジェットコースターがある。ある人がこのジェットコースターに乗るのだが、怖さの閾値Lを越えない範囲でなるべく楽しみたい。ある区間で目を開けているとFi楽しめて、怖さがDi増える。目を閉じていると怖さがK下げる。楽しさの最大値はいくらか。
1<=N<=1000
1<=K<=500
1<=L<=300000
1<=F<=20
1<=D<=500

解法

DP[n][f]を考える。DP[n][f]は区間がnで楽しさがfの時にできる怖さの最小値を表す。あとはこれを計算するだけ。