NOIP练习题。
f[i]f[i]f[i]表示去的时候选了iii且回来的时候第一步走的是i−1i-1i−1的最优值。
显然f[i]=maxf[i]=maxf[i]=max{f[j]−sum[j]f[j]-sum[j]f[j]−sum[j]}+sum[i−2]+a[i]+a[i−1]+sum[i-2]+a[i]+a[i-1]+sum[i−2]+a[i]+a[i−1]
直接上单调队列优化就行了。
注意有可能只跳前kkk个直接回到原点的情况。
代码：
#include<bits/stdc++.h>#define N 250005#define ll long longusing namespace std;inline ll read(){ll ans=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans*w;}int n,k,q[N],hd,tl;ll ans=0,f[N],a[N],sum[N];int main(){n=read(),k=read(),hd=1,tl=0;for(int i=1;i<=n;++i)sum[i]=sum[i-1]+max((a[i]=read()),0ll);for(int i=1;i<=n;++i){while(hd<=tl&&i-q[hd]>k)++hd;f[i]=f[q[hd]]+sum[i-2]-sum[q[hd]]+a[i]+a[i-1];while(hd<=tl&&f[q[tl]]-sum[q[tl]]<f[i-1]-sum[i-1])--tl;q[++tl]=i-1;}for(int i=1;i<=n;++i)ans=max(ans,sum[min(i+k-1,n)]-sum[i]+f[i]);printf("%lld",max(ans,sum[k]));return 0;}
