BZOJ 2442: [Usaco2011 Open]修剪草坪 单调队列

Description

在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，
新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。

然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N
(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，
奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。

靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，那么，这些奶牛就会罢工
去开派对:)。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中
没有连续的超过K只奶牛。

Input

* 第一行：空格隔开的两个整数N和K

* 第二到N+1行：第i+1行有一个整数E_i

Output

* 第一行：一个值，表示FJ可以得到的最大的效率值。

题解：

定义 $f_{i}$ 表示不选 $i$ 的最优价值.
则有 $f_{i}=max(f_{j}-sum_{j})+sum_{i-1}$
用单调队列维护一下 $max(f_{j}-sum_{j})$ 即可.
注意一下 $j$ 的合法范围，适当时候弹掉.  

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define setIO(s) freopen(s".in","r",stdin)

#define N 100010

#define ll long long

using namespace std;

ll n, k, maxn, ans, head = 1, tail = 1;

ll c[N], sum[N], dp[N], q[N], a[N];

ll max(ll a,ll b )

{

    return a > b ? a : b;

}

int main() {

   // setIO("input");

    scanf( "%lld%lld", &n, &k );

    for(ll i = 1; i <= n; i++ )

    {

        scanf( "%lld", &c[i] );

        sum[i] = sum[i - 1] + c[i];

    }

    ll ans=0;

    for(ll i = 1; i <= n + 1; i++ ) {

        while( head <= tail && q[head] < i - k - 1 ) head++;

        dp[i] = dp[q[head]] - sum[q[head]] + sum[i - 1];

        ans=max(ans,dp[i]);

        while( head <= tail && dp[q[tail]] - sum[q[tail]] <= dp[i] - sum[i] ) tail--;

        q[++tail] = i;

    }

    printf( "%lld\n", ans);

    return 0;

}