传送门
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 long
using 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;
}