[CF1768F] Wonderful Jump

首先设 $f_i$ 为从 $1$ 跳到 $i$ 的最小花费，$O(n^2)$ DP 是简单的。

观察性质。首先，如果 $a_k\le a_j,a_k\le a_i$，那么 $i\to j$ 的转移一定是不优于 $i\to k\to j$ 的。

其次，考察 $j\to i$ 的转移，若 $i-j\ge\frac n{a_i}$，那么有 $a_i(i-j)^2\ge(i-j)n$，也即该转移不优于 $j\to j+1\to\cdots\to i-1\to i$。

所以只需从前往后遍历每个位置 $i$，向前枚举 $j$，直到 $a_j\le a_i$ 或 $i-j\le\dfrac n{a_i}$，进行 $j\to i$ 的转移；再向后枚举 $j$，直到 $a_j\le a_i$ 或 $j-i\le\frac n{a_i}$，进行 $i\to j$ 的转移即可。

上述两个性质分别保证了两种优化的正确性，现在来证明其复杂度。

对于不超过 $\sqrt n$ 的数，最多有 $O(\sqrt n)$ 种，每个数向前向后枚举遇到相同数就会停止，所以每一种数带来的的总复杂度为 $O(n)$。

对于超过 $\sqrt n$ 的数 $a_i$，向前/向后枚举的次数为 $\frac n{a_i}\le\sqrt n$。

综上，总复杂度为 $O(n\sqrt n)$。