一道有意思的 \(\text{dp}\) 呀。
思路
我们容易发现，一个点最多会往回走一次。
也就是每一个点最多被遍历三次。
因此，我们可以考虑每个点的贡献。
\[dp_i=\min_{j=1}^{i-1}dp_j+x_i-x_j+\max(2\times(x_i-x_{j+1}),T)
\]
其中，\(dp_i\) 表示前 \(i\) 个金币全部取完，此时位于第 \(i\) 个位置。
这个式子很容易维护。
我们不妨分类讨论。
- \(2\times(x_i-x_{j+1})>T\)
那么，我们只要维护 \(dp_i-x_i-2\times x_{j+1}\) 的最小值即可。 - \(2\times(x_i-x_{j+1})\le T\)
由于 \(n\) 只有 \(10^5\)，那么我们用暴力维护上述式子。
因为 \(2\times(x_i-x_{j+1})\) 是在不断变大的。
那么我们只需要用堆维护一下（也可以用单调队列，堆更好写）。
代码就很好写了。
Code
AC记录。