AGC032 D - Rotation Sort - ツバサの備忘録

解法

シフトという操作が少しわかりづらいのですが、結局は

任意の要素を取り出し、別の任意の位置に挿入する(現時点より左に挿入するならコストは $B$ 、右であれば $A$ )

という操作ができることになります。
ので、それぞれの要素を、右側に移動してそろえる、左側に移動してそろえる、操作しない、の3パターンに割り振ればよいです。
右側に操作するか左側に操作するか、というのは、今作成中の順列で操作しなかった要素の右端を見ればよいです。

$dp[i][j] = i$ 番目の要素まで並べた上で、操作しなかった要素の右端が $j$ であるようなもののなかで可能な最小コスト

とします。
$dp[i][j] = \left\{\begin{array}{} dp[i][j] + B \ (a_{i} \lt j)\\ min(dp[i][k])(ただし k \lt j) \ (a_{i} = j) \\ dp[i][j] + A \ (a_{i} \gt j) \\ \end{array}\right.$

という遷移を行えばよいです。
$dp[0][0] = 0$ が初期値、 $min(dp[n][j])$ が答えです。