题目描述

blablabla

样例

blablabla

算法

维护一个递减的单调队列即可,不知道为啥放在dp里,不过我也是真的菜,学了dp就只想dp…

(单调队列) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N<<1];
int rea=0,front=1,q[N<<1];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; }
    //求ai+aj+min(abs(i-j),n-abs(i-j)).
    //我们不妨维护n/2的单调队列.单调队列和单调栈差不多,你只要清楚它是干什么的就好了.
    int m=(n<<1);
    int k=(n>>1);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        //维护一个递减序列即可.
        while(front<rea&&q[front]<i-k) front++;//维持front即可.
        ans=max(ans,a[i]+a[q[front]]+i-q[front]);
        //再拿我当前的位子怼掉比我小的数.
        while(a[i]-i>a[q[rea]]-q[rea]&&rea>=front) rea--;
        q[++rea]=i;
    }
    printf("%d\n",ans);
    return 0;
}