$$\color{Red}{修剪草坪 【（换元法解决单调队列）】}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。
现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。
然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。
FJ 有 N 只排成一排的奶牛，编号为 1 到 N。
每只奶牛的效率是不同的，奶牛 i 的效率为 Ei
编号相邻的奶牛们很熟悉，如果 FJ 安排超过 K 只编号连续的奶牛，那么这些奶牛就会罢工去开派对。
因此，现在 FJ 需要你的帮助，找到最合理的安排方案并计算 FJ 可以得到的最大效率。
注意，方案需满足不能包含超过 K 只编号连续的奶牛。
输入格式
第一行：空格隔开的两个整数 N 和 K；
第二到 N+1 行：第 i+1 行有一个整数 Ei
输出格式
共一行，包含一个数值，表示 FJ 可以得到的最大的效率值。
数据范围
1 ≤ N ≤ 10 ^ 5
0 ≤ Ei ≤ 10 ^ 9
输入样例：
5 2
1
2
3
4
5
输出样例：
12
样例解释
FJ 有 5 只奶牛，效率分别为 1、2、3、4、5。
FJ 希望选取的奶牛效率总和最大，但是他不能选取超过 2 只连续的奶牛。
因此可以选择第三只以外的其他奶牛，总的效率为 1 + 2 + 4 + 5 = 12。
思考
我的滑动窗口题解 这道题就是单调队列的思想
可以点入我的题解，看一下基本的单调队列做法的思想是什么。
这道题首先第一直觉肯定能想到我们肯定要使用前缀和，方便我们随时计算。
子序列的长度是点的个数还是边的个数？
子序列的长度通常指包含的元素个数。
之前的滑动窗口的大小，其实和子序列的长度表示的含义是一致的。
它进行位移判断使用的是 if (hh <= tt && q[hh] < i - k + 1) hh ++;
这里 i - k + 1的值代表的是滑动窗口的左端点应该在的位置，当此时这个位置的索引位置已经超越我们单调队列的最左边的元素的下标，代表这个元素已经不在我们维护的范围内了，需要把它从队列移除。
这里我们先根据闫式DP分析法，构建状态方程 f[i]，代表从1 -> i 头奶牛中选取，且符合效率最高的集合。故状态属性为MAX，最大值。
我们分析自然要从最简单的划分 ： 选不选第 i 头奶牛开始
① 不选： f[i-1]即代表不选的情况，所表示的集合和状态值
② 选： 那么选一定要满足合法的角度选，且还要求效率最高，我们有着不能超过 K 的连续奶牛限制，故我们进一步划分状态需要考虑第 i 头奶牛位于的序列长度是多少来划分。
显然我们能选到最长的情况是 从 i - k + 1这头一直选到 i
最短的情况是 i 自己构成一个序列，而 i - 1不选
我们设选取的区间长度为j, 为了满足序列长度的限制，显然： i - j位置的奶牛一定不能选取，要不然就连接到我们最后的序列里面了，长度就不对了。
故前面的序列选取状态，可以用 f[i - j - 1]表示
此时状态方程为：
f[i] = max(f[i - j - 1] + s[i] - s[i - j])
同时，我们枚举的时候，会固定 i去枚举 j 故，其实 s[i]是常数
我们变形：
f[i] = max(f[i - j - 1] - s[i - j]) + s[i]
此时我们知道, k 代表选取的区间长度 1 <= j <= k
我们不妨使用换元法： 设 g(x) = f[x - 1] - s[x]，此中 x = i - j
故自变量 x 的取值范围为： i - k <= x <= i - 1
故显然选取的 i，依赖的范围就是 i - k <= x <= i - 1的点
这里我们需要思考一个边界问题：
当 x = 0即 i = j时，显然会出现 f[-1]，数组越界
那么什么情况下才会出现这样的情况？
f[x - 1] = f[i - j - 1] 代表的区间是选取了后面的固定区间，排除间隔点后，之前的区间内选取的状态。
当出现 i = j的情况下，说明：我们是从第一个数一直选到 i，且区间长度小于等于 K
那么这种情况下，显然直接使用 f[i] = s[i] - s[i - j]计算即可，即s[i]，故方程此时应该设置为0
数组已经默认是 0 了，但是其他的题可能未必，所以判断是必要的，并且是这道题的关键。
java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = (int) 1e5 + 10, n, m;
static int[] q = new int[N];
static long[] s = new long[N];
static long[] f = new long[N];
static long g(int x){
return f[Math.max(0, x - 1)] - s[x];
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for (int i = 1; i <= n; i++) s[i] = Integer.parseInt(br.readLine()) + s[i - 1];
int hh = 0, tt = 0;
for (int i = 1; i <= n; i++) {
if (hh <= tt && q[hh] < i - m) hh ++;
f[i] = Math.max(f[i-1], g(q[hh]) + s[i]);
while (hh <= tt && g(i) >= g(q[tt])) tt --;
q[++ tt] = i;
}
System.out.println(f[n]);
}
}
