二刷提高课，题解目录在这里— 提高课的题解目录

所有的优化都是从暴力得来的
观察题目得知，只要选择连续不超过k的，一直选即可
所以需要枚举断点在哪里，是一个集合问题，这里用DP
f[i]从1~i选择结果效率最大，很明显我们可以通过第i个选或者不选来划分
不选很简单，可是如果选了，我们接下来如何考虑呢？
我们选择了i为了使得考虑到所有情况，所以我们需要枚举前面k位
意为选择了i并选择了前面k位的情况然后空一位再+f[j]
为何要空一位？因为我们状态表示的是从1~i选择效率最大
所以有可能中间连续选择了k位，如果我们不空一位就会出现选择k+1位导致错误
那么倘若我们每次都去枚举前面k位则会导致超时
既然我们每次选择的都是最大值，为何不适用单调队列来做呢
从而避免重复枚举前面k位

这里讲解一下为何单调队列中有时tt初始化为-1有时初始化为0
效果一样吗？很明显不！
当我们的问题枚举的时候要用使0这一位为0来作为对比时（像这里的前缀和）使用的是0
当我们的问题枚举的是第i位时（像多重背包单调队列优化）使用的是-1

#include<iostream>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll a[N];
int q[N];
int n,k;
ll f[N];
ll g(int x)
{
    return f[x-1]-a[x];
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt&&q[hh]<i-k)hh++;
        f[i]=max(f[i-1],g(q[hh])+a[i]);
        while(hh<=tt&&g(q[tt])<=g(i))tt--;
        q[++tt]=i;
    }
    cout<<f[n];
    return 0;
}