考虑dist(i,j)实际就是在把1,n连上之后形成的环上的(i,j)间最小距离.
dp无法直接处理环,考虑断环为链,将A复制一遍接到后面
在这条长为2n的链上,找出$max${$A_i+A_j+i-j\ |\ i> j,i-j\le n/2$}
于是$O(n^2)$做法就很容易了.
考虑如果存在$j<j’,a[j]+(j’-j)<a[j’]$,则只要$j’$合法,$j$一定无法产生贡献.
于是,用单调队列进行优化,复杂度$O(n)$
可能是由于用了STL的deque
,跑了611ms.
//Wan Hong 3.0
//notebook
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <deque>
typedef int ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 1000011
ll a[MAXN<<1|1];
std::deque<ll>q;
int main()
{
ll n=read(),ans=0;
for(ll i=1;i<=n;++i)a[i+n]=a[i]=read();
q.push_back(1);
for(ll i=2;i<=(n<<1);++i)
{
while(!q.empty()&&q.front()<i-(n/2))q.pop_front();
umax(ans,a[q.front()]+a[i]+(i-q.front()));
while(!q.empty()&&a[q.back()]+(i-q.back())<a[i])q.pop_back();
q.push_back(i);
}
printf("%lld",ans);
return 0;
}