奇妙跳跃：题解

思路

令 $dp_i$ 表示到达位置 $i$ 的最小费用，朴素转移为

$$dp_i=\min_{j<i}\left(dp_j+\min_{j\le x\le i}a_x(i-j)^2\right).$$

关键性质是：最优转移区间的最小值一定出现在某个端点。若最小值 $a_k$ 只出现在内部 $j<k<i$，则拆成 $j\to k\to i$ 后费用变为

$$a_k\big((k-j)^2+(i-k)^2\big)<a_k(i-j)^2,$$

原转移不可能最优。

做法

取阈值 $B=650$，分三类枚举端点最小值转移。

1. 直接枚举距 $i$ 不超过 $B$ 的全部左端点，并向左维护区间最小值。
2. 当右端点 $a_i\le B$ 时，向左枚举到第一个 $a_j\le a_i$。固定一个小值后，各次扫描区间互不重叠，总量为 $O(nB)$。
3. 维护一个栈，保存值严格递增且不超过 $B$ 的候选左端点。枚举栈中至多 $B$ 个位置，处理区间最小值出现在左端点的远距离转移。

为什么可以忽略两端值都大于 $B$ 的远跳？逐格跳的费用至多为 $n(i-j)$。若一次长度为 $d$ 的跳跃最优，则

$$B d^2<n d,$$

从而 $d<n/B\le B$；这种转移已经被第一类枚举。

三类合并后覆盖全部可能的最优转移。

复杂度

时间复杂度为 $O(nB)=O(n\sqrt n)$，空间复杂度为 $O(n)$。

子任务算法

• $n\le500$：枚举所有 $j<i$ 并维护区间最小值，复杂度 $O(n^2)$。
• 所有 $a_i=c$：二次函数是凸的，拆成单位跳最优，故 $dp_i=c(i-1)$。
• $a_i\le80$：取 $B=80$，只需小值端点扫描与单调候选栈，复杂度 $O(80n)$。
• 无限制：使用根号分治算法。