Python3 解法, 执行用时: 257ms, 内存消耗: 30252K, 提交时间: 2023-04-29 15:15:51

import sys

f = [0] * 200010 
q = [0] * 200010

n, m = map(int, sys.stdin.readline().split())
w = list(map(int, sys.stdin.readline().split()))
w.insert(0, 0)

hh = 0
tt = 0
f[0] = 0
for i in range(1, n + 1):
    if q[hh] < i - m:
        hh += 1
    f[i] = f[q[hh]] + w[i]
    while hh <= tt and f[q[tt]] >= f[i]:
        tt -= 1
    tt += 1
    q[tt] = i
res = 1e9
for i in range(n - m + 1, n + 1):
    res = min(res, f[i])

print(res)

C++ 解法, 执行用时: 36ms, 内存消耗: 1912K, 提交时间: 2021-11-14 15:02:16

#include<bits/stdc++.h>
using namespace std;
int a[200001],f[200001],q[200001];
int main(){
	int n,m,l = 1,r = 1,i;
	cin>>n>>m;
	for (i = 1;i <= n;i++)
		cin>>a[i];
	for (i = 1;i <= n;i++){
		while (l <= r && i - q[l] > m)
			l++;
		f[i] = f[q[l]] + a[i];
		while (l <= r && f[q[r]] > f[i])
			r--;
		q[++r] = i;
	}
	int ans = f[n];
	for (i = n - m + 1;i < n;i++)
		if (f[i] < ans)ans = f[i];
	cout<<ans;
	return 0;
}