题解 P1725 【琪露诺】

Eric100911 · 2018-10-22 12:46:00 · 题解

首先，这道题目转移方程并不难想:

然后，数据量高达200000，绝对不可能用传统的O(n^2)双重循环

再分析，会发现其中一维的复杂度被用于寻找定长带修区间最值，因而可以对症下药

利用单调队列，维护一个长r-l+1的区间最值

本人使用结构体封装好的单调队列实现，结合快读，即可解决，代码附上

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
struct monoqueue{
    #define data int  //鄙人蒟蒻，不会template  
    int head,tail,pos[MAXN];
    data num[MAXN];
    void clear(){head=1;tail=0;}
    bool empty(){return head>tail;}
    data front(){return num[head];}
    data back(){return num[tail];}
    void push(data x,int p,int len,bool MODE){//MODE为0时设定为升序单调队列 
        if(MODE){
            while(x>=num[tail]&&head<=tail) tail--;
            num[++tail]=x; pos[tail]=p;
            while(pos[head]<=p-len&&head<=tail) head++;
        }
        else{
            while(x<=num[tail]&&head<=tail) tail--;
            num[++tail]=x; pos[tail]=p;
            while(pos[head]<=p-len&&head<=tail) head++;
        }//带分类的push
    }
    void out(){
        for(int i=head;i<=tail;i++) cout<<num[i]<<' ';
        cout<<endl;
    }
};
monoqueue Q;
int A[MAXN],dp[MAXN<<1],N,L,R;
inline int read(){
    register int x=0;
    register bool f=1;
    register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=0;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return f?x:-x;
}
int main(){
    register int ans=-2147483647;
    N=read(),L=read(),R=read();
    for(int i=0;i<=N;i++) A[i]=read();
    Q.clear();
    for(int i=L;i<N+L;i++){
        dp[i]=Q.front()+A[i];
        Q.push(dp[i-L+1],i-L+1,R-L+1,1);
        //Q.out();cout<<endl;
    }
    for(int i=N;i<N+R;i++) ans=max(ans,dp[i]);
    cout<<ans<<endl;//令人舒心的一行
    return 0;
}