环路运输

环路运输

给出一个长度为n序列(a_i),定义第i个位置和第j个位置的距离为(s[i][j]=min(|i-j|,n-|i-j|)),定义两个位置的权值为(a_i+a_j+s[i][j]),询问最大的权值,(nleq 10^6)

注意到所谓的距离,即环上的距离公式,所以问题与环有关,于是拆环成链,再补一截一模一样的序列在原序列后,不妨按照区间问题的解决办法,枚举一个右端点i,再枚举左端点j,自然(i>j),设(i-jleq n/2)

(i-jleq n/2:)

此时,显然可以在新序列上表现旧序列i,j的距离

(i-j> n/2)

此时存在另外一个(j'=j+n),满足i,j'间距离(j'-i=j+n-i=n-|i-j|)

于是只要在环上满足(i-jleq n/2),就可以表现原序列也即环的所有的距离,其实也可以这样感性理解,因为所谓的再补一截,也就是一条穿越原来的环2次的路径,对于其中一小段路径的长度记做s1,对于这一小段路径的两个端点,在环上互达有两条路径,较小的那条为距离,于是当(s1leq n/2),必然为所谓的距离。

于是我们只要枚举右端点,在枚举合法的左端点,寻找它们的最大值,这个我们时是可以利用单调递减的单调队列维护的。

参考代码:

#include <iostream>
#include <cstdio>
#include <deque>
#define il inline
#define ri register
#define pi pair<int,int>
using namespace std;
deque<pi>Q;
int a[2000001];
il int max(int,int);
int main(){
    int n,n2,ans(0);scanf("%d",&n),n2=n<<1;
    for(int i(1);i<=n;++i)scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i(1),j;i<=n2;++i){
        while(Q.size()&&Q.front().first<i-(n>>1))Q.pop_front();
        if(Q.size())ans=max(ans,Q.front().second+a[i]+i);
        while(Q.size()&&Q.back().second<a[i]-i)Q.pop_back();
        Q.push_back(make_pair(i,a[i]-i));
    }printf("%d",ans);
    return 0;
}
il int max(int a,int b){
    return a>b?a:b;
}

原文地址:https://www.cnblogs.com/a1b3c7d9/p/10931751.html