Aimee

转移方程很好想$dp_{i,0/1}$表示第i个选（1）或不选（0）

其中$dp{i,0}=max(dp{i-1,0},dp_{i-1,1})$

而$dp_{i,1}=max(dp[j]+sum_i-sum_j),i-j<=k$

都有$sumi$,那就成了$dp{i,1}=max(dp[j]-sum_j)+sum_i,i-j<=k$

显然括号里的可以用单调队列优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int queue[2000001];
int h,t=1;
int n,k;
int cow[2000001];
int dp[2000001][2];
int sum[2000001];
int v[2000001];
signed main(){
    scanf("%lld%lld",&n,&k);
//  k--;
    for(int i=1;i<=n;++i){
        scanf("%lld",&cow[i]);
        sum[i]=sum[i-1]+cow[i];
    }
    for(int i=1;i<=n;++i){
        while(queue[h]<i-k&&t>h){
            h++;
        }
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=v[queue[h]]+sum[i];
        int z=dp[i][0]-sum[i];
        while(z>v[queue[t-1]]&&t>h){
            t--;
            //v[t]=0;
        }
        queue[t++]=i;
        v[i]=z;

    }
    cout<<max(dp[n][0],dp[n][1])<<endl;
    return 0;
}