復元いる？？？？

解説

値が無駄にでかいので、[1, n]に座圧で収めましょう。

初期位置は値が0だとすると実装が楽です。

ここでdpを2つ考えます。

dp1[i][j] := 今数字iを取ろうとしていて、iを1つも取っていないときjにいるような最小値

dp2[i][j] := 今数字iを取ろうとしていて、iを全て取り終えてjにいるような最小値

dp1[i][j]の更新は簡単で、

$dp1[i][j] ← \min _ {k} (dp1[i][j], dp2[i - 1][k] + dist(k, j))$

です。dp2の更新を考えましょう。

f:id:jupiro:20201118083803p:plain

ここで上の図で考えましょう。

橙と赤が今取ろうとしてるiを指しています。

赤の位置を $j$ として、赤の位置で終わるのはどのような場合が最適かを考えます。 f:id:jupiro:20201118084658p:plain

1つは反時計回りで一番近いところにいる位置からぐるとっと時計まわりで取る方法です。

反時計回りで一番近いところを $k$ として、 $dp2[i][j] ← \min(dp2[i][j], dp1[i - 1][k] + clockwisedist(k, j))$

f:id:jupiro:20201118084955p:plain

もう1つは時計回りで一番近いところにいる位置からぐるっと反時計回りで取る方法です。

時計回りで一番近いところを $k$ として、 $dp2[i][j] ← \min(dp2[i][j], dp1[i - 1][k] + counterclockwisedist(k, j))$

なお、以下の実装では $clockwisedist(k,j) = counterclockwisedist(j, k)$

の性質を利用しています。

以上で求めることができました。

復元はがんばれ！！

提出コード