由于要考虑距离的问题,也就是比较$\mid i-j\mid,N-\mid i-j\mid$的大小,
分类讨论一下,不妨设$1\le j<i\le N$。
若$i-j\le N/2$,有$A_i+A_j+i-j$
若$i-j>N/2$,有$A_i+A_j+N-i+j=A_i+A_j+(j+N)-i$
因此可以转为在长度$2N$的道路上运输货物的最大代价。
这个过程可以用单调队列优化一下,维护一下$A_j-j$的最大值,限制条件是$i-j\le N/2$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=1e6+5;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int q[N<<1],a[N<<1];
int main()
{
int n;qr(n);
for(int i=1;i<=n;i++)qr(a[i]),a[i+n]=a[i];
int l=1,r=1;q[1]=1;int ans=0;
int m=n>>1;
for(int i=2;i<=n+(n+1>>1);i++)
{
while(l<=r&&i-m>q[l])++l;
ans=max(ans,a[i]+a[q[l]]+(i-q[l]));
while(l<=r&&a[q[r]]-q[r]<=a[i]-i)--r;
q[++r]=i;
}
qw(ans);puts("");
return 0;
}
最后一次更新于2019-10-25
0 条评论