dp+根号分治，配得上省选题的难度。
一眼 dp，虽然暴力肯定过不了，但是把朴素转移先列出来绝对没坏处。
dpi=1≤j<imin(dpj+j≤k≤iminak×v)
这个东西很难用 DS 维护，有 min 的存在又很难斜优啥的，就想到有一种方法优化：限制可行状态数。
假设要求从 i 跳到 j。若一步从 i 到 j 是最优的，那么它的花费一定小于一步一步跳的花费，即
i≤k≤jminak×(i−j)2≤(i−j)×n
这是因为值域上界为 n。
化简一下，得到
i≤k≤jminak≤i−jn
看到分数就可以想到根号分治。
-
i−j≤n 时，暴力枚举 j 转移。时间复杂度 O(n)。
-
i−j>n 时，枚举 i≤k≤jminak。又因为有一个性质：最优情况下一定有 k=i 或 k=j。因为 ((i−k)2+(k−j)2)×ak≤(i−j)2×ak。这时又可以分两种情况。
-
k=j 时，记录每一个 ≤n 的数上一次出现的位置，每次枚举转移。时间复杂度 O(n)。
-
k=i 时，如果 ai≤n，从 i 往前暴力枚举转移，直到遇到一个 ak≤ai 为止。这一部分的复杂度呢？根据楼上大佬的说法，“对于 [1,n] 内的每个值，最多可能扫完整个序列一次”。所以均摊复杂度 O(n)。
总时间复杂度 O(nn)。其他的不说，这个分讨的复杂度太优美了。
Submission
