[USACO11OPEN]Mowing the Lawn G

 我们根据dp方程可以找到我们所需要维护的.

我们发现  dp[j-1]-sum[j]  是我们所需要维护的 , 但是 j 是需要 i-k ~ i 显然单调队列可以排上用场:

我们对于一个 i 要去找一个 j 使得最大 

#include

#define int long long
using namespace std;
const int N=3e5+7;

int n,k;
int a[N];
int sum[N];
int dp[N],q[N];
int t[N];
int head,tail=1;

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        //前缀和,方便计算j~i (即上一个断点到i的和 
    }
    //dp[i]=max{dp[j-1]-sum[j]} +sum[i] (对于j 
    //维护dp[j-1]-sum[j] 
    for(int i=1;i<=n;i++)
    {
        t[i]=dp[i-1]-sum[i];
        // 队尾是当前值 
        while(head<=tail&&t[q[tail]]<t[i])
        tail--;//如果左边有 比他的大的就可以出队 
        q[++tail]=i;
        //保持头是最大 
        while(head<=tail&&q[head]k)
        head++;
        //如方程 
        dp[i]=t[q[head]]+sum[i];
    }
    
    cout<<dp[n];
    return 0;
}