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

本文主要是介绍『单调队列优化DP』[POI2014]ZAL-Freight，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{Problem}$

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

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

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

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

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

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

$\mathrm{Solution}$

设 $f_i$ 表示第 $i$ 辆火车返回的最短时间。则有： $f_i= \min\{\max(a_i,f_j+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{head}-1]$ 来更新答案即可。

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

$\mathrm{Code}$

#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; 
}