题解 | 空间跃迁

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
long long a[N],f[N];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<n;i++){
        cin>>a[i];
    }
    long long sum=0;
    if(k==0){
        for(int i=1;i<n;i++){
            sum+=a[i];
        }
        cout<<sum<<endl;
        return 0;
    }
    else if(n-1>k){
        long long max_j=0;
        for(int i=1;i<n;i++){
            f[i]=f[i-1]+a[i];
        }
        for(int i=1;i<=n-k;i++){
            max_j=max(f[i+k]-f[i],max_j);
        }
        sum=f[n-1]-max_j;
        cout<<sum<<endl;
    }
    else{
        cout<<0<<endl;
    }
    return 0;
}