[AGC007D] Shik and Game 题解

一道有意思的 \(\text{dp}\) 呀。

思路

我们容易发现，一个点最多会往回走一次。

也就是每一个点最多被遍历三次。

因此，我们可以考虑每个点的贡献。

其中，\(dp_i\) 表示前 \(i\) 个金币全部取完，此时位于第 \(i\) 个位置。

这个式子很容易维护。

我们不妨分类讨论。

1. \(2\times(x_i-x_{j+1})>T\)
   那么，我们只要维护 \(dp_i-x_i-2\times x_{j+1}\) 的最小值即可。
2. \(2\times(x_i-x_{j+1})\le T\)
   由于 \(n\) 只有 \(10^5\)，那么我们用暴力维护上述式子。
   因为 \(2\times(x_i-x_{j+1})\) 是在不断变大的。
   那么我们只需要用堆维护一下（也可以用单调队列，堆更好写）。

代码就很好写了。

Code

AC记录。