[Codeforces] Educational Codeforces Round 95 (Rated for Div. 2) C. Mortal Kombat Tower

問題

方針

友人の行動は、ボスを倒すまたはボスをスキップすることができます。また、自分と友人は最低でも \( 1 \) 体のボスに対応しなければならなく、\( 1 \) 回のセッションで最大で \( 2 \) 体のボスを倒すことができます。

ここで友人が \( i \) 番目のボスを同一セッションで \( 1 \) 体目のボスであるときのスキップした回数を \( f(i, 0) \) とし、同一セッションで \( 2 \) 体目のボスであるときのスキップした回数を \( f(i, 1) \) とします。同様に \( g(i, 0), g(i, 1) \) を定義します。

初期値は、\( f(1, 0) = a_1\) となり、その他は \( \infty \) で初期化します。更新式は、

\begin{eqnarray}
f(i + 1, 0) &=& \min(g(i, 0), g(i, 1)) + a_{i+1}\\
f(i + 1, 1) &=& f(i, 0)+ a_{i+1}\\
g(i + 1, 0) &=& \min(f(i, 0), f(i, 1))\\
g(i + 1, 1) &=& g(i, 0)
\end{eqnarray}

となります。

コード