题解 P1725 【琪露诺】

XUCHENGHUI · 2017-03-16 18:30:59 · 题解

由于数据范围很大，所以DP得优化。

这里就想到一个单调队列，维护一个单调递减的队列，在i时，将之前i-min(l,r)+1加入队中。找到打的就将之前小的弹出。

并用place和s1维护位置，就可以一直使用当前最大值。

最后多循环min(l,r)-1次，求出答案

#include<cstdio>
#include<cstdlib>
using namespace std;
int i,j,k,n,m,top,s1,s2,l,r,x1,x2;
int a[200005],f[200005],p[200005];
struct stevenson
{
    int place;
    int num;
}q[200005];
int read(void) {         //读入优化
    char c; while (c=getchar(),(c<'0' || c>'9') && c!='-'); int x=0,y=1;
    if (c=='-') y=-1; else x=c-'0'; 
    while (c=getchar(),c>='0' && c<='9') x=x*10+c-'0'; return x*y;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int main()
{
    n=read(); l=read(); r=read(); x1=max(l,r); x2=min(l,r); q[0].num=2e9; s1=1; s2=x2-1;
    for(int i=0;i<=n;i++) a[i]=read(); 
    for(int i=x2;i<=n+x2-1;i++)
    {
        s2++;
        if(i-x1>q[s1].place) s1++;
        f[i]=a[i]+q[s1].num; p[i]=s2;
        while(f[i-x2+1]>q[top].num&&top>=s1) 
        top--;
        top++;
        q[top].num=f[i-x2+1]; q[top].place=p[i-x2+1]; 
    }
    printf("%d",f[n+x2-1]);
    return 0;
}