Hop Hop Hamstring

解説

階段を $L$ 段登る行動を何回連続で行ったかによって、その後に選べる行動が変わります。

そこで、$dp_{i,j}$ を「$i$ 段目にいるときの支払金額の最小値」とします。状態 $j$ は次を表します。

• $j=0$：肉離れをしておらず、直前に $L$ 段登る行動をしていない
• $j=1$：肉離れをしておらず、$L$ 段登る行動を $1$ 回連続で行った
• $j=2$：肉離れをしておらず、$L$ 段登る行動を $2$ 回連続で行った
• $j=3$：すでに肉離れをしている

初期状態は $dp_{0,0}=0$ で、それ以外は十分大きい値とします。

$1$ 段登る場合、肉離れをしていなければ連続回数は $0$ に戻るため、$j=0,1,2$ について $dp_{i+1,0}\leftarrow\min(dp_{i+1,0},dp_{i,j}+A_{i+1})$ と更新します。

すでに肉離れをしている場合は、$dp_{i+1,3}\leftarrow\min(dp_{i+1,3},dp_{i,3}+A_{i+1})$ と更新します。

$L$ 段登る場合、連続回数が $0$ または $1$ なら、$j=0,1$ について $dp_{i+L,j+1}\leftarrow\min(dp_{i+L,j+1},dp_{i,j}+A_{i+L})$ と更新します。

連続回数が $2$ の状態からさらに $L$ 段登ると肉離れを起こすため、$dp_{i+L,3}\leftarrow\min(dp_{i+L,3},dp_{i,2}+A_{i+L}+K)$ と更新します。

肉離れをした後は、$L$ 段登る行動を選ぶことはできません。

以上の遷移を段数の小さい順に行えば、それぞれの状態に到達する最小金額を求められます。答えは $\min_{0\leq j\leq 3}dp_{N,j}$ です。

計算量

状態数は $O(N)$ で、各状態からの遷移は定数個なので、計算量は $O(N)$ です。