\(k\) 回目に乗ったアトラクションを \((c_i, v_{i,1}), (c_i, v_{i, 2}), \dots\) と分けて考え, アトラクションが増えた状態と見なす. このとき, \(k\) 回目に乗らずに \(k+1\) 回目に乗る場合は同じ待ち時間で満足度が低くなるので, このような場合は最適解にはなりえないので, このようなケースは無視して考えても問題ない.

この状態で \(i\) 番目のアトラクションまで見たときに待ち時間が \(j\) となるときの最大の満足度を \(C(i, j)\) とすると,

\[C(i, j) = \max \{ C(i-1, j), C(i-1, j-c_i) + v_i \}\]

となる. これを DP で解く.