1087 修剪草坪（单调队列优化）

清疚 2022-09-14 09:57 161阅读 0赞

**1. 问题描述：**

在一年前赢得了小镇的最佳草坪比赛后，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

**输出样例：**

**样例解释**

FJ 有 5 只奶牛，效率分别为 1、2、3、4、5。FJ 希望选取的奶牛效率总和最大，但是他不能选取超过 2 只连续的奶牛。因此可以选择第三只以外的其他奶牛，总的效率为 1 + 2 + 4 + 5 = 12。  
来源：[https://www.acwing.com/problem/content/description/1089/][https_www.acwing.com_problem_content_description_1089]

**2. 思路分析：**

分析题目可以知道这道题目属于最优化问题，而且数据规模比较大，所以我们考虑使用**动态规划**的思路来解决，可以发现状态定义还是比较容易想出来的，我们可以定义一个一维数组f，其中f\[i\]表示1~i头奶牛中没有安排连续超过k头奶牛能够获得的最大收益，怎么样进行状态计算呢？状态计算对应集合的划分，一般是找最后一个不同点，我们可以以第i头牛选或者不选划分为两个集合，对于不选第i头牛的集合恰好可以表示为f\[i - 1\]，但是对于选第i头牛集合无法直接进行出结果所以需要对集合进一步划分（在划分集合的时候无法直接计算结果的时候则需要进一步的划分直到能够计算出最终的结果为止），我们可以按照以i为右端点连续选择的奶牛的头数进行划分，也即枚举以i为右端点的连续的区间长度为1，2，3...k ，可以发现当区间长度最大为k对应的位置为x，则x的上一个位置是不能够选的，如果选择了那么长度就会超过了k了，所以当选第i头牛的时候可以表示为f\[i\] = f\[i - j - 1\] + s\[i\] - s\[i - j\]，1 <= j <= k，其中s为前缀和，可以整理一下方程将方程变化的部分移到一边得到f\[i\] = max(f\[i - j - 1\] - s\[i - j\]) + s\[i\]，1 <= j <= k；这样就可以得到选第i头奶牛与不选第i头奶牛能够获得的最大收益的状态方程；我们其实可以使用g(i - j)来表示变化的部分：f\[i - j - 1\] - s\[i - j\]，也即g(t)表示为f\[t - 1\] - s\[t\]，在具体实现的时候可以使用一个函数g计算得到结果，并且我们需要考虑一下边界，也即g(0) = ?，g(0) = f(-1) - s(0) = f(-1)，也即i = j的时候这个时候表示的是以i为右端点选择的连续区间的长度为i，且i <= k，所以是满足条件的，这个时候f(-1) = 0，所以g(0) = 0，在计算结果之前特判一下即可。可以发现求解的是长度为k的最值问题，使用**单调队列优化**即可。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def g(self, i: int, f: List[int], s: List[int]):
            # i = 0为边界表示以i为右端点选择一段长度为i的连续区间i - 1 = -1此时g(0) = 0
            if i == 0: return 0
            return f[i - 1] - s[i]
    
        def process(self):
            n, k = map(int, input().split())
            w = [0]
            for i in range(n):
                w.append(int(input()))
            s = [0]
            # 预处理前缀和
            for i in range(1, n + 1):
                s.append(s[-1] + w[i])
            q = [0] * (n + 1)
            hh, tt = 0, 0
            f = [0] * (n + 1)
            for i in range(1, n + 1):
                # 边界, 可以画图确定
                if q[hh] < i - k: hh += 1
                # 计算1~i头奶牛中不选第i头奶牛的获得的最大收益和选第i头牛并且在所有以i为右端点连续长度小于等于k的情况下能够获得的最大价值
                f[i] = max(f[i - 1], s[i] + self.g(q[hh], f, s))
                # 维护f[i - j - 1] - s[i - j]的最大值, 根据状态转移方程进行维护
                while hh <= tt and self.g(i, f, s) >= self.g(q[tt], f, s): tt -= 1
                tt += 1
                q[tt] = i
            return f[n]
    
    
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_description_1089]: https://www.acwing.com/problem/content/description/1089/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d381a86eda404f1fbc3e8dc85a6c606d.png