题解：P10957 环路运输

· · 题解

看到绝对值先把它拆了，原式等价于：

a_i+a_j+i-j & j<i,i-j\leq \frac n 2 \\ a_i+a_j+n+j-i & j<i,i-j>\frac n 2 \end{cases}

至于 j\geq i 的情况，显然没有意义，因为我们只需要枚举 j<i 的情况就可以得出答案。

然后看到环先把它拆成链，n\gets n\times 2。

那么原式的第二条也没有意义了，变为：

dp_{i,j} = a_i+a_j+i-j~~~~(j<i,i-j\leq \frac n 2)

所以我们要从前往后枚举，此时原式看起来像是单调队列优化，所以考虑变形（从前往后枚举）：

dp_i = \max\{a_j-j\}+a_i+i~~~~(i-j\leq \frac n 2)

好了，我们只需要维护 \max\{a_i-i\} 就行了，后面的条件就是 pop 队头的条件，队头是最大的 a_i-i。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1;
int n,a[N],q[N],h,t,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=n*2;i++){
        while(h<=t&&i-q[h]>n/2) h++;
        if(h<=t) ans=max(ans,a[i]+a[q[h]]+i-q[h]);
        while(h<=t&&a[q[t]]-q[t]<=a[i]-i) t--;
        q[++t]=i;
    }
    cout<<ans;
}