Tag：线性DP + 单调队列优化

状态： f[i] 代表前 i 个中选取不超过连续 m 个的最大值。属性：MAX

状态转换：对于最后一个元素 i，有选和不选两种方式。

1. 不选择第 i 个元素，则情况转化为 f[i-1] 。（无需考虑连续的问题）

2. 选择第 i 个元素，则情况转化为， 对于选择的最后连续的一段， 选几个最好？

设选择了 j 个，其中(1 <= j <= m)，因为至少要选 i 号元素，至多不能超过m个。

转移方程为：

​ f [ i ] = max{ s[ i ] - s[ i - j ] + f [ i - j - 1 ] } ( 1 <= j <= k)

​ = max{ f [ i - j - 1 ] - s [ i - j ] } + s [ i ]

​ 如果将max函数内部的运算看作 g( i - j ) 的话，相当于建立一个单调队列，维护 g(i - j )的递减序列， 由于 j 的限制是 (1 <= j <= k)，则维护 i 之前 最多 k 个即可。

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

const int N = 1e5+10;
typedef long long LL;
LL a[N];
LL s[N];
LL f[N];
int q[N];
int n,m;

LL g(int i)
{
    return f[i-1] - s[i];
}

int main()
{
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        s[i] = s[i-1] + a[i];
    }

    int hh=0, tt=0;
    LL res = 0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh] < i-m) hh++;
        f[i] = max(f[i-1],s[i] + g(q[hh]));     //注意利用闫氏DP分析法时，分成了选i和不选i两种，而单调队列是对选i进行了优化，还有和不选i
        //即f[i-1]进行比较
        while(hh<=tt && g(q[tt]) <= g(i)) tt--; //维护递减子序列
        q[++tt] = i;
    }

    cout<<f[n]<<endl;

    return 0;
}