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

思路：

• $1. 状态表示$
  $集合：从前\ i\ 头牛里面选得到的价值$
  $属性：\max$

• $2. 状态转移$
  $不选第i头牛：f[i]=f[i-1]$
  $选择第i头牛：f[i]=f[j-1]+s[i]-s[j]\ (i-m\le j\le i-1)$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n,m;
int q[N];
LL s[N],f[N];

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

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

    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-m) hh++;
        f[i]=max(f[i-1],g(q[hh])+s[i]); //在 [i - m, i - 1] 中找一个最大的 g
        while(hh<=tt&&g(q[tt])<=g(i)) tt--; //严格单调递减，队头即最大值
        q[++tt]=i;
    }

    cout<<f[n]<<endl;

    return 0;
}