$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：以\ i\ 为右端点，选择第\ i\ 个元素的代价的集合$
  $属性：\min$

• $2. 状态转移$
  $f_i=\min\{f_j\}+w_i\ (i-m\le j\le i-1)$
  $res=\min\{f_i\}\ (n-m+1\le i\le n)$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;

int n,m;
int w[N];
int q[N];
int f[N];

int main()
{
    cin>>n>>m;

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

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-m) hh++; //队头出列
        f[i]=f[q[hh]]+w[i]; //f[i] = min{f[j]} + w[i] (i - m <= j <= i - 1)
        while(hh<=tt&&f[q[tt]]>=f[i]) tt--; //严格单调递增，队头即最小值
        q[++tt]=i;
    }

    int res=1e9;
    for(int i=n-m+1;i<=n;i++) res=min(res,f[i]);

    cout<<res<<endl;

    return 0;
}