题目描述

在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。

现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。

然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。

FJ 有 N 只排成一排的奶牛，编号为 1 到 N。

每只奶牛的效率是不同的，奶牛 i 的效率为 Ei。

编号相邻的奶牛们很熟悉，如果 FJ 安排超过 K 只编号连续的奶牛，那么这些奶牛就会罢工去开派对。

因此，现在 FJ 需要你的帮助，找到最合理的安排方案并计算 FJ 可以得到的最大效率。

注意，方案需满足不能包含超过 K 只编号连续的奶牛。

数据范围

$1≤N≤10^5,$
$0≤Ei≤10^9$

样例

输入
5 2
1
2
3
4
5

输出
12

算法1

单调队列优化Dp $O(n)$

根据闫式Dp分析法：
f[i] 表示在前i头牛中所有的合法选择方案中的最大效率值。

那么根据第i头牛选或不选可以分成两个集合：

• 1.不选择第i头牛，那么f[i] = f[i-1];

• 2.选择第i头牛，根据题意，所有的方案不能包含选择连续K头奶牛，那么既然选择了第i头牛，可以根据第i头牛所在的连续序列的长度对此集合进一步划分：

  • 1.序列长度为k, f[i] = f[i-k-1] + s[i] - s[i-k];
  • 2.序列长度为k-1, f[i] = f[i-(k-1)-1] + s[i] - s[i-(k-1)];
    ....
  • 3.序列长度为1, f[i] = f[i-1-1] + s[i] - s[i-1];(边界，当前i个奶牛全选时，且i不大于K，f[-1]=0)

所以状态转移: f[i] = max(f[i-1], f[i-j-1]-s[i-j]+s[i]), j∈[1,k]
令g(i,j) = f[i-j-1] - s[i-j],在状态转移方程中，s[i]是确定的，所以只需要找到f[i-j-1]-s[i-j]的最大值，即g(i,j)的最大值，由于j有范围限制，所以可以使用单调队列来优化状态转移。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+100;

int a[N];
LL s[N];
int q[N];
LL f[N];   //f[i] 表示在前i头牛中所有合法法案的最大效率值
int n,m;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;

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

    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]);
        while(hh<=tt && g(q[tt]) <= g(i)) tt--;
        q[++tt] = i;
    }

    cout<<f[n];

    return 0;
}