题解 P1725 【琪露诺】

· · 题解

优秀的唯一手写deque请看这里

首先第一个想法一定是DP

如果用f[i]表示到i位置的最大冰冻值 那么

f[i]=max(f[i],a[i]+f[j]) (i-l<=j<=i-r)

我表示这种dp纯属套路，如果不会的话就去多做题ba

然后好看一点就是

f[i]=max(f[j])+a[i] (i-l<=j<=i-r)

然后看到

说明 对于60%的数据：N <= 10,000 说明这样一定会T

考虑到Dp状态转移方程的单调性就知道只需求f[j]最值

所以参考单调队列 不会的请 ☞☞☞ P1886 滑动窗口

然后讲一下有几个小细节讲一下（由于数据水我被卡在10,80调了一会儿）

1.暴力把f[i]压入单调队列(emmm)

2.在head+r（即极限右端）小于i时 队头弹掉

3.在i位置把a[i+1-l]压入队列（个人写法比较好写)

4.在head+l>i最开始时不转移

5.在head+l>i单调队列不更新

细节好多啊（雾) 实测55ms

#include<bits/stdc++.h>
using namespace std;
const int Maxn=200010;
int a[Maxn],dp[Maxn],n,l,r,head=1,tail=0,ans;
struct data{
    int pos,val;
};
data deq[Maxn];
inline int read(){
    int e=0,f=1;
    char c;
    while(!isdigit(c=getchar())){ if(c=='-') f=-1;}
    do{ e=(e<<1)+(e<<3)+c-48; }
    while(isdigit(c=getchar()));
    return e*f;
}
int main(){
    n=read();n++;
    l=read();
    r=read();
    ans=-1e9;
    memset(dp,0xf3,sizeof(dp));
    dp[1]=0;
    deq[head]=data{1,dp[1]};
    for(register int i=1;i<=n;++i){ a[i]=read(); }
    for(register int i=2;i<=n;++i){
        if(deq[head].pos+r<i) head++;
        if(deq[head].pos+l<=i) dp[i]=deq[head].val+a[i];
        if(i-l<0) continue;
        while(dp[i-l+1]>=deq[tail].val&&head<=tail) tail--;
        deq[++tail]=data{i-l+1,dp[i-l+1]};
    }
    for(register int i=n-r;i<=n;++i) ans=max(ans,dp[i]);
    cout<<ans;
}