https://class.51nod.com/Html/Textbook/Problem.html#problemId=3978&textbookChapterId=724
https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337
这里一次发车的转移是 \([j+1,i]\),出发时间 \(+s\) 为 \(j+1\) 启程返回,偏移 \(i-j-1\) 就轮到当前车了。
最后一个式子min中下面的部分错了,应该再加一个 \(i-1\)。
而且 \(G[j]-2j\) 也是单调不降的,所以我们就可以每次弹出队首直到 \(G[j]-j-1\ge T[i]-i\),这样最终队首前一个位置就是上面情况的最值(\(-j\) 单调减),而队首是下面情况的最值(因为单调不降),两者取最值。
插入都在尾部,弹出都在开头。
如果弹空了,此时只有上面情况,\(j=i-1\);如果队首恰好是 \(0\),那么上面情况不存在,只要队列不空,就有下面的情况。
\(O(n)\)
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1000010;
int n,t[N],q[N];
ll f[N],s;
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n>>s;
t[0]=-1;
for(int i=1;i<=n;++i)cin>>t[i],t[i]=max(t[i],t[i-1]+1);
memset(f+1,0x3f,n*8);
int hh=0,tt=0;
#define j q[hh]
for(int i=1;i<=n;++i){
while(hh<=tt&&f[j]-j-1<t[i]-i)++hh;
ll K=hh>tt?i-1:j-1;
if(K>=0)f[i]=s-1ll+s+i+t[i]-K;
if(hh<=tt)
f[i]=min(f[i],s+s-2ll+i+i+f[(K+1)]-(K+1)-(K+1));//
q[++tt]=i;
}
cout<<f[n];
return 0;
}
标签:列车,51nod,队首,int,hh,单调,3978,最值
From: https://www.cnblogs.com/wscqwq/p/18323838