Div2 1023 F1

类似 CSP-S2023 的 T2 ，都是短小精悍的 DP。

首先观察到，操作只有两种，一是直接超过，代价为 $a_i$，二是通过超能力，将 $a_i$ 和 $a_j$ 调换，代价为 $j-i(j > i)$。

我们发现，想到达一个目的地，可以将前面较小的数字换过来，之后一直把这个1小数字换到前面再超过，如下：

以此类推，每回把 $2$ 提过去超越，再调回来，再超越，直到终点。

假设我们目前在位置 $x$，被调换的数字在位置 $y$,目的地是 $p$,显然，代价为 $x-y-1$ （把 $a_x$ 换到你所在位置的前一个），加上 $(x-p)\times a_y$ （超越 $a_y$ 所花费的），加上 $x-p-1$ (把 $a_y$ 向前换，跟着我们走的花费)

总代价整理得 $(x-p)\times a_y + x+x-y-p-2$。

可以证明，要前往位置 $p$，我们所选的应该是 $[p,x]$ 间 $a_y$ 最小的值 (值相同的越靠右越优)

证明：不妨设 $a_{y1} < a_{y2} (y1 ,y2\in [p,x])$。

则

上下式子相减得

可以证明，因为 $y1,y2 \in [p,x]$,所以 $y1-y2 < x-p$ ,又因为 $(a_{y1}-a_{y2}) \ge 1$，所以上述式子小于 $0$。

故选择 $a_y$ 最小的最优

转移很显然，设 $dp_i$ 表示目前我在位置 $i$，抵达 $1$ 所需的最小代价，则按式子

转移即可

其中，$pos \in [j,i-1]$，指最小值的下标 , $mi$ 指其中最小值

时间复杂度 $O(n^2)$