思路：

很容易退出DP方程: f i = m i n ( f j ) + a i f_i=min(f_j)+a_i fi​=min(fj​)+ai​ 其中 i − m ≤ j < i i-m≤j<i i−m≤j<i 然后直接用单调队列维护

c o d e code code

#include<iostream>
#include<cstdio>

using namespace std;

int n, m;
int a[101010];
int q[101010], f[101010];

int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);
	int hd=1, tl=1;
	q[1]=0;
	for(int i=1; i<=n; i++)
	{
		while(hd<=tl&&q[hd]<i-m)
			hd++;
		f[i]=f[q[hd]]+a[i];
		while(hd<=tl&&f[i]<=f[q[tl]])
			tl--;
		q[++tl]=i;
	}
	int ans=1e9;
	for(int i=n-m+1; i<=n; i++)
		ans=min(ans, f[i]);
	printf("%d", ans);
	return 0;
}