洛谷 P3580 - [POI2014]ZAL-Freight(单调队列优化 dp)

洛谷题面传送门

考虑一个平凡的 DP:我们设 \(dp_i\) 表示前 \(i\) 辆车一来一回所需的最小时间。

注意到我们每次肯定会让某一段连续的火车一趟过去又一趟回来,故转移可以枚举上一段结束位置,设为 \(j\),那么有转移

\[dp_i=\min\limits_{j}\{\max(dp_j+i-j-1,a_i)+2s+i-j-1\}
\]

在这里我们不妨假设 \(a_i<a_{i+1}\),这个可以通过从左到右扫一遍并执行 \(a_i\leftarrow\max(a_{i-1}+1,a_i)\) 实现。

稍微解释一下上面的式子,由于一趟来回,那么我们肯定会让前面的车都等到第 \(i\) 辆车到达对面后再返回,而第 \(i\) 辆车发车的时间是 \(\max(dp_j+j-i-1,a_i)\),因此第 \(i\) 辆车到达对面的最早时间就是 \(\max(dp_j+j-i-1,a_i)+s\)。而全部 \(j-i+1\) 辆车返程的时间又是 \(s+j-i+1\),总时间就是 \(\max(dp_j+j-i-1,a_i)+2s+j-i-1\)。

如何优化?考虑单调队列。我们考虑拆 \(\max\)。如果 \(dp_j+i-j-1\ge a_i\),也就是 \(dp_j-j\ge a_i-i+1\),\(\max\) 会取到 \(dp_j+i-j-1\),此时 \(dp_j+2s+2i-2j-2\leftarrow dp_i\),我们维护 \(dp_j-2j\) 的最大值即可实现,具体来说,根据 \(dp\) 数组的实际含义,有 \(dp_j-j\) 是单调不降的,因此我们考虑维护一个 \(dp_j-j\) 递增,\(dp_j-2j\) 递减的单调队列,每次 pop 掉队首直到队首元素符合 \(dp_j-j\ge a_i-i+1\)​ 然后用它更新答案即可。

如果 \(dp_j+i-j-1<a_i\),那么 \(a_i+2s+i-j-1\leftarrow dp_i\),因此我们只用维护 pop 出去的元素的 \(-j\) 的最小值即可,而由于我们是按照 \(j\) 递增的顺序将 \(j\)​​ 的贡献加入单调队列的,因此 \(-j\) 的最小值肯定在上一个被 pop 出去的元素处取到,直接更新答案即可。

时间复杂度线性。

感觉和 AGC 007D 有点像(

应该是 CSP 之前除了模拟赛之外刷的最后一道题了(

using namespace fastio;
const int MAXN=1e6;
int n,s,a[MAXN+5],q[MAXN+5],hd=1,tl=1;ll dp[MAXN+5];
ll calc(int x,int y){return max(1ll*a[y],dp[x]+y-x-1)+2*s+y-x-1;}
int main(){
read(n);read(s);a[0]=-1;
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) a[i]=max(a[i-1]+1,a[i]);
memset(dp,63,sizeof(dp));dp[0]=0;
for(int i=1;i<=n;i++){
while(hd<tl&&dp[q[hd]]-q[hd]<a[i]-i+1) ++hd;
if(hd<=tl) chkmin(dp[i],calc(q[hd],i));
if(hd>1) chkmin(dp[i],calc(q[hd-1],i));
while(hd<tl&&dp[q[tl]]-2*q[tl]>=dp[i]-2*i) --tl;
q[++tl]=i;
}
printf("%lld\n",dp[n]);
return 0;
}
上一篇:【HDU 6021】 MG loves string (枚举+容斥原理)


下一篇:实现hibernate 的validator校验