ABC197E Traveler - geam1113’s diary

解説を見て解きました。

問題文の条件は、同じ色を連続して全て取ってから次の色を取るということを示します。

入力例1なら、32123の順で並んでいるボールを12233の順で取ります。同じ数字内での取り方に指定はありません。

ある色 $i$ のボールを全て取ることを考えます。

色 $i$ の中で、最も小さい座標を $L_i$ 、大きい座標を $R_i$ とします。

どのような順番でボールを取ったとしても、必ず $L_i$ ⇔ $R_i$ 間の移動が発生します。

そのため、この移動の際に全てのボールを回収することにしても問題ありません。

このように考えると、ボールの取り方は以下の2パターンしかありません。

次の色のボールを取得するときは、最後にボールをとった地点からの移動のみを考えればよく、これは $L_i$ と $R_i$ の2パターンの状態しかありません。

よって、以下の $dp$ が考えられます。

$dp[i][j]:=$ 色 $i$ において、最後に $j$ にいるときの最小値。

但し、 $j=\{0,1\}$ とし、0のときは $L_i$ 、1のときは $R_i$ にいるとします。

遷移は、

の4パターンに基づいて行えばよいです。

実装上、

としておきます。