动态规划例题 (1)

TP Link
Submission

我们考虑 $a_p$，我们可以这样做：

• 花费 $i-p$ 把 $a_p$ 换到自己前面
• 花费 $a_p$ 超车
• 再花费 $1$ 把 $a_p$ 换到自己面前
• 再花费 $a_p$ 超车……

于是我们可以利用 $a_p$ 超车一个区间 ($[l,r],l\le p\le r$) 的车手，花费为（假设当前正在 $r$ 的身后）

当我们从 $r$ 向 $l$ 扫描的时候，此时我们枚举的 $p$ 递减，因此 $r-p$ 递增，要使这个式子最小，$a_p$ 必须为 $[l,r]$ 内最小值（且最靠右），才有可能最小化这个式子。

解决完这个区间之后，我们发现，整个 $[1,n]$ 可以切分成多个这样的子结构（每个小区间里选出自己的 $a_p$）。差不多就类似于走进另一个区间发现在另一个区间用另一个数当 $a_p$ 更划算。

现在我们来定义状态。设 $dp[i]$ 表示从第 $n$ 个人后面走到第 $i$ 个人后面、第 $i+1$ 个人前面时所需要的最小费用。那么 $dp[0]$ 就是我们需要的答案，初始化 $dp[n]=0$.

随后，我们从后向前枚举 $i$（现在在第 $i$ 个人后面），并且枚举 $j$，表明我们要从 $i$ 走到 $j$ 位置，即 $dp[i]\to dp[j]$.

根据上文的分析，我们需要知道 $a[j\dots i]$ 的最小值 $a[p]$（有多个的话取最右的，这个可以在枚举 $j$ 时一起维护）

因为 $a[p]$ 考虑了 $a[j]$，所以 $j$ 位置也会被超车，因此更新的是 $dp[j-1]$