C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;
int n,m;
int w[N],f[N];

int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>w[i];

    deque<int>q;
    q.push_back(0);
    for(int i = 1;i<=n;i++){
        if(q.size()&&q.front()<i-m)q.pop_front();
        f[i] = f[q.front()]+w[i];
        // cout<<i<<"  "<<f[i]<<endl;
        while(q.size()&&f[i]<=f[q.back()])q.pop_back();
        q.push_back(i);
    }
    int ans = 1e9;
    for(int i = n-m+1;i<=n;i++)
        ans = min(ans,f[i]);
    cout<<ans<<endl;


    return 0;
}