bzoj2442

题解：

单调队列+dp

f[i]=max(f[j-1]+sum[i]-sum[j])

然后维护f[j-1]-sum[j]单调性

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

int n,m,a[N],p[N];

ll sum[N],q[N],f[N];

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++)scanf("%d",&a[i]);

    for (int i=;i<=n;i++)sum[i]=sum[i-]+a[i];

    f[]=a[];p[]=;q[]=-a[];

    int l=,r=;

     for (int i=;i<=n;i++)

     {

         if (p[l]+m<i)l++;

         f[i]=sum[i]+q[l];

         while (l<=r&&q[r]<=f[i-]-sum[i])r--;

         p[++r]=i;q[r]=f[i-]-sum[i];

     }

    printf("%lld",f[n]);

}