题目描述

在一年前赢得了小镇的最佳草坪比赛后，Farm John变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farm John希望能够再次夺冠。
然而，Farm John的草坪非常脏乱，因此，Farm John只能够让他的奶牛来完成这项工作。Farm John有 $n(1 \le n \le 100000)$ 只排成一排的奶牛，编号为 $1\sim n$。每只奶牛的效率是不同的，奶牛i的效率为 $e_i(0 \le e_i \le 1,000,000,000)$ 。
靠近的奶牛们很熟悉，因此，如果Farm John安排超过 $k$ 只连续的奶牛，那么，这些奶牛就会罢工去开派对 :)。因此，现在Farm John需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过 $k$ 只奶牛。

输入格式

第一行：空格隔开的两个整数 $n$ 和 $k$
第二到 $n+1$ 行：第 $i+1$ 行有一个整数 $e_i$

输出格式

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

输入输出样例

输入 #1

5 2
1
2
3
4
5

输出 #1

12

思路

（因为我很菜，所以我的方法是一步一步求的，应该不难理解）

看到这题肯定首先考虑DP。

因为题目中说不能有超过 $k$ 只连续的牛排列在一起，我们不妨设 $f_{i,j}$ 为在前 $i$ 只牛中，最后有 $j$ 只牛排列在一起的最大效率和，这样只需要保证 $0\le j\le k$ 就可以了。

容易得出以下转移：

\[\begin{align} &f_{i,j}=f_{i-1,j-1}+e_i\\ &f_{i,0}=\max_{0\le j\le i-1}\{f_{i-1,j}\} \end{align}\]

这样就算是维护出 $f_{i-1,j}$ 的最大值，时间与空间复杂度还均为 $O(n^2)$， $n\le 100000$， 显然会炸。

我们想办法删掉一维。在结果查询时，我们可以直接查询 $f_{n+1,0}$ 就足够了（假设有 $n+1$ 头牛，且最后一个不选，那么就是 $n$ 头牛任意选且没有超过连续 $k$ 头牛），所以我们考虑将第二维删去。

观察式子，发现我们可以将 $(1)$ 式代入 $(2)$ 式，就可以推出下面的式子：

\[\begin{aligned} f_{i,0}&=\max_{0\le j\le i-1}\{f_{i-1,j}\}\\ &=\max_{0\le j\le i-1}\{f_{i-2,j-1}+e_{i-1}\}\\ &=\max_{0\le j\le i-1}\{f_{i-3,j-2}+e_{i-1}+e_{i-2}\}\\ &\ \ \ \ \ \ \ \ \ \ \ \vdots\\ &=\max_{0\le j\le i-1}\{f_{i-j-1,0}+e_{i-1}+e_{i-2}+\cdots+e_{i-j}\}\\ \end{aligned}\]

这样，我们就成功的将第二维消掉了。
后面这一串加和是一段连续区间的和，我们可以考虑用前缀和优化，设 $pre_i=e_1+e_2+\cdots+e_i$，那么原式可以继续化为：

\[\begin{aligned} f_{i,0}&=\max_{0\le j\le i-1}\{f_{i-j-1,0}+e_{i-1}+e_{i-2}+\cdots+e_{i-j}\}\\ &=\max_{0\le j\le i-1}\{f_{i-j-1,0}+pre_{i-1}-pre_{i-j-1}\}\\ \end{aligned}\]

其中，$pre_{i-1}$ 是不变的，我们可以将它提出：

\[\begin{aligned} f_{i,0}&=\max_{0\le j\le i-1}\{f_{i-j-1,0}+pre_{i-1}-pre_{i-j-1}\}\\ &=\max_{0\le j\le i-1}\{f_{i-j-1,0}-pre_{i-j-1}\}+pre_{i-1}\\ \end{aligned}\]

可以发现，大括号里都存在 $i-j-1$， 这样看起来太复杂了，我们不妨设 $w=i-j-1$，由 $0\le j\le i-1$ 推出 $i-k-1\le w\le i-1$ （这不用推了吧，初中不等式知识），原式继续化为：

\[\begin{aligned} f_{i,0}&=\max_{0\le j\le i-1}\{f_{i-j-1,0}-pre_{i-j-1}\}+pre_{i-1}\\ &=\max_{i-k-1\le w\le i-1}\{f_{w,0}-pre_{w}\}+pre_{i-1}\\ \end{aligned}\]

我们已经把第二维消掉了，所以我们可以重新定义一下 $f$：

设 $f_i$ 为前 $i$ 头牛中，不选第 $i$ 头牛，且满足没有连续超过 $k$ 头牛，可以获得的最大效率和，则有：

\[f_{i}=\max_{i-k-1\le w\le i-1}\{f_{w}-pre_{w}\}+pre_{i-1}\\\]

如果你做过 滑动窗口 这道经典单调队列的题，不难发现，我们只需要维护一个递减的单调队列，维护信息为 $f_w-pre_w$ ，就可以每次 $O(1)$ 的求出 $\max_{i-k-1\le w\le i-1}{f_{w}-pre_{w}}$ 了。

使用单调队列优化后，空间与时间复杂度均为 $O(n)$ ，完全足够。

注意/提示

这应该写不炸吧