『单调队列优化DP』[POI2014]ZAL-Freight

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

Upper Bytown和Lower Bytown的火车站通过一条轨道铁路连接。

沿任何一个方向在它们之间行驶都需要s分钟。

但是，离开车站的火车必须至少间隔一分钟。

而且，在任何时候，铁路上的所有列车都必须朝同一方向行驶。

根据我们的时间表，前往下拜镇的n列货运列车将通过上拜镇。 他们将在下拜敦装载货物，然后返回上拜敦。 为简单起见，我们假设将货物装载到火车上几乎不需要时间。

我们将确定最后一班火车返回Upper Bytown的最短时间。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

设$f_i$表示第$i$辆火车返回的最短时间。则有： f i = min ? { max ? ( a i , f j + i ? j ? 1 ) + i ? j ? 1 + 2 S } f_i= \min\{\max(a_i,f_j+i-j-1)+i-j-1+2S\} fi?=min{ max(ai?,fj?+i?j?1)+i?j?1+2S}

因此，我们的首要做法就是拆除$\max$函数。

• 当$f_j?j\ge a_i?i+1$时，有：$$f_i=(f_j?2j)+2(i+S?1)$$
  此时我们使用单调队列维护$f_j?2j$的最小值即可。
• 当$f_j?j<a_i?i+1$时，有：$$f_i=(a_i+i+2S?1)?j$$
  此时我们只要找到满足上述条件的下标最大值即可。

考虑如何解决后者，联系单调队列优化DP的性质：

• 元素都是依次加入队列的。
• 最新弹出的一定是下标最大的。

因此我们只需要用$q[\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}?1]$来更新答案即可。

小陷阱：为了保证$a_i?i+1$单调不下降，即“移动窗口”是有序向右移动的，我们遇见两个$a_i$相同的时候，我们需要将第二个$a_i$赋值为$a_i+1$，以保证单调队列的有序性。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N = 2e6;int n, S;
int a[N], f[N], q[N];int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}signed main(void)
{
    n = read(), S = read();memset(f,30,sizeof f); f[0] = 0;for (int i=1;i<=n;++i) a[i] = read();sort(a+1,a+n+1);int head = 1, tail = 1;for (int i=1;i<=n;++i) {
    #define updata(i,j) f[i] = min(max(f[j] + i - j - 1, a[i]) + i - j - 1 + 2 * S, f[i])while (head <= tail && f[q[head]] - q[head] < a[i] - i + 1) head ++;while(head <= tail && f[q[head]] - q[head] < a[i] - i + 1) head ++;if (head <= tail) updata(i, q[head]); updata(i, q[head-1]);while (head <= tail && f[q[tail]] - 2 * q[tail] >= f[i] - 2 * i) tail --;q[++tail] = i;}cout << f[n] << endl;return 0; 
}