Div2 1023 F1

· · 题解

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

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

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

第一步 \\ 4,2,5,7,me \\第二步\\4,5,7,2,me\\第三步\\4,5,7,me,2\\第四步\\4,5,2,me,7\\第五步\\4,5,me,2,7

以此类推，每回把 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])。

则

\begin{cases} (x-p)\times a_{y1} +x+x- y1-p-2\\ (x-p)\times a_{y2} +x+x- y2-p-2 \end{cases}

上下式子相减得

y2-y1+(a_{y1}-a_{y2})\times (x-p)

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

故选择 a_y 最小的最优

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

dp_j=\min(dp_j,dp_i+(i-j)\times mi + i+i-j-pos-2)

转移即可

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

时间复杂度 O(n^2)

代码