有一个数轴，上面有 \(n\) 个点，坐标为 \(a_1,\cdots,a_n\)。
你一开始在位置 \(S\)，你可以以 \(1\) 的速度行走。
令 \(t_i\) 表示第一次走到第 \(i\) 个点的时间，最小化 \(\sum t_i\)。
\(n \le 10^6\)
一般的 dp 方法，设 \(dp_{L,R,0/1}\) 表示已经走过 \([L,R]\)，目前站在那一侧的答案，是难以做到低于 \(O(n^2)\) 复杂度的。
尝试是否能将左右的贡献分开。
我们给每个点预先分配一个贡献：如果点 \(i\) 已经被经过，那么贡献就是它被经过的时间；否则它的贡献是以最快方式抵达它时的时间。
此时可以发现：如果钦定某个时刻向右走，那么所有你右侧的点在你走动时不会产生贡献！
令 \(f_i (a_i\le S)\) 表示走到点 \(i\)，最小的总贡献和(\(g_i\) 表示 \(i>S\) 的贡献)，这是可以转移的！
具体来说：
\[f_i = \min_j\{ g_j+2(a_j-a_i)(n-j)\} \\ g_i = \min_j\{ f_j+2(a_i-a_j)(j-1)\} \]感受一下可以知道存在线性做法。
标签：表示,le,个点,min,贡献,经典,区间,dp From： https://www.cnblogs.com/havzriu/p/17119853.html