单调队列优化DP

暴力做法的第二重循环是循环连续的k个区间的最小值，由此可以用单调队列维护最小值

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int f[N];
int n,m;
int a[N];
int q[N];

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

    int hh = 0,tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if(i - m > q[hh])hh++;
        f[i] = f[q[hh]] + a[i];
        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;
}