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