题解 P1725 【琪露诺】

田阙西 · 2018-08-17 22:04:51 · 题解

費了九牛二虎之力終於a掉了這題。。。

首先我們要找到dp方程：

F[i]=max{f[k]}+a[i] , i-r<=k<=i-l, k>=0

千萬記住左邊是i-r，右邊是i-l！！！

我爲了這個wa了無數次。。。

由於只和f[k]的值以及編號有關，我們可以用單調隊列維護。

stl大法好！！ （不過不太建議noip選手使用。。。 我是因爲不會手寫才勉强用stl的）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,l,r,ans=-2000000000;
int f[200001*2],a[200010*2];
struct mmm{int v,num;};
deque <mmm> q;
mmm x;
int fastRead()
{
    int f=1,re=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){re=re*10+c-'0';c=getchar();}
    return f*re;
}
int main()
{
    n=fastRead(),l=fastRead(),r=fastRead();
    for(int i=0;i<=n;i++)
    {
        a[i]=fastRead();
    } 
    memset(f,128,sizeof(f));
    f[0]=0;x.num=0;x.v=0;q.push_back(x);
    for(int i=l;i<=n+r;i++)
    {
        while(!q.empty()&&q.front().num<(i-r))q.pop_front();
        if(f[i-l]>-2000000)
        {
            x.v=f[i-l];x.num=i-l;
            while(!q.empty()&&q.back().v<=x.v)q.pop_back();
            q.push_back(x);
        }   
        if(!q.empty())f[i]=q.front().v+a[i];
    }
    for(int i=n+1;i<=n+r;i++)
    ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}