No.37

$i$ 番目のアトラクションに2回目以降に乗ったときの満足度を計算し, $ci, vi$ に追加しておく.

このとき, 2回目に乗るためには1回目に乗る必要があるといった考慮は必要ない. なぜならば, 最大満足度を得るためには2回目に乗るときには1回目はすでに乗っているはずだからである.

あとは経過時間 $t$ のとき, $i$ 番目のアトラクションまで調べたときの最大満足度を $V(t,i)$ とすると,

$$V(t,i) = \max(V(t, i - 1), V(t - ci, i - 1) + vi)$$

となり, これを DP で計算して, $V(\ast, (ciの長さ))$ の最大値を計算する.