python

6.2 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`AcWing` `1087`. 修剪草坪

一、题目描述

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

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

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

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

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

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

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

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

输入格式 第一行：空格隔开的两个整数 N 和 K；

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

输出格式 共一行，包含一个数值，表示 FJ 可以得到的最大的效率值。

数据范围 1≤N≤10^5,0≤E_i≤10^9

输入样例：

输出样例：

样例解释 FJ 有 5 只奶牛，效率分别为 1、2、3、4、5。

FJ 希望选取的奶牛效率总和最大，但是他不能选取超过 2 只连续的奶牛。

因此可以选择第三只以外的其他奶牛，总的效率为 1 + 2 + 4 + 5 = 12。

二、暴力作法

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
typedef long long ll;
int a[N];
ll s[N], f[N];

/*
BruteForce
通过了 9/12个数据
*/
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

    // 暴力大法
    for (int i = 1; i <= n; i++)
        for (int j = i; j >= i - m; j--)
            f[i] = max(f[i], f[j - 1] + s[i] - s[j]);

    cout << f[n] << endl;
    return 0;
}

三、动态规划

考虑用 动态规划 来求解本问题

由于 连续选择 超过 m 个元素时，这些元素的贡献为 0 （相当于没选）

而本题，所有的元素值都是 正整数，故我们的方案中，连续选择的元素数量 一定是 不超过 m个的

状态表示

f[i]:以第i个数为结尾的所有数字中,连续长度不超过m,贡献总和最大值。

我们来分析一下这个最优状态可能由哪些状态转移而来。

举个栗子：

假设m=3，现在讨论一下第6头牛，它这个位置有两种选择，选与不选：

不选：由于第6头没有发挥作用，现在的 最大贡献和与前面的最大贡献和一致:

$$\large f[6]=f[6-1]=f[

选择：如果它选了，那么它前面的就不是随意的了，需要有范围限制，人脑模拟一下：最大连续选择长度不能超过3,所以讨论以下情况：
- 假设本轮取3个最优：
```
\large f[6]=a[6]+a[5]+a[4]+ ? 
```
- 假设本轮取2个最优：
```
\large f[6]=a[6]+a[5]+?'
```
- 假设本轮取1个最优：
```
\large f[6]=a[6]+?''
```

注:不是能取3个取3个值就最大了，因为你取了3个，意味着前面第4个就不能取，这合不合适就不一定了。

为啥要加?呢？以3个为例，如果取3个最优，那么此时取到了4号结点位置，3号肯定是不能取的！原因很简单，如果取上，就是连续4个了，超过了m限定！那3左侧是随意的，这时，f[2]的含义是在前2个元素中合法并可以获取到的最大值，现在的情况可以直接表示为f[2],同理得到：

$\large f[6]=a[6]+a[5]+a[4]+f[2] \ \large f[6]=a[6]+a[5]+f[3] \ \large f[6]=a[6]+f[4]$

a[6]+a[5]+a[4]这样的东东，很显然是前缀和的基本表示式，提示我们引入前缀和进行思考。如果预处理了前缀和，那么就有：

利用 前缀和 思路优化一轮：

\large f[6]=s[6]-s[3]+f[2] \large f[6]=s[6]-s[4]+f[3] \large f[6]=s[6]-s[5]+f[4]

通用化处理一下：(6就是固定的当前值i,而3,4,5是可变的，我们设为j，同时j是有范围的，也就是i-m \sim i-1)

\large f[i]=s[i]-s[j]+f[j-1] ~~~ j \in [i-m,i-1]

在i确定的情况下，s[i]是固定的，变化的就是f[j-1]-s[j],要想求f[i]最大值，就是求f[j-1]-s[j]的最大值，而j是有范围的,这就转化为一个区间内取极大值问题，可以 用单调队列来优化。

单调队列优化办法

① 维护一个队列，记录距离i前面的m个区间范围内，f[j-1]-s[j]取值最大
② 这个最优的序号j，就是队列头的记录序号q[hh]
③ 因为队列中不包含i结点，所以需要在i进入队列前，while上方进行计算更新结果

时间复杂度

O(n)

四、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
typedef long long LL;
int q[N];
LL s[N], f[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

    // 由于滑动窗口在i的左边，需要讨论前缀和的s[l-1],第1个没有前序，不符合整体的代码逻辑，添加了一个哨兵
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i++) {
        // 　1、年龄大于m的老家伙们，不管是不是实力够强大，一概去死
        while (hh <= tt && i - q[hh] > m) hh++;

        // 因为滑动窗口在i 左侧，先使用再加入
        f[i] = max(f[i - 1], f[max(0, q[hh] - 1)] + s[i] - s[q[hh]]);

        // 　2、不如我年轻，并且，不如我有实力的老家伙们去死
        while (hh <= tt && f[i - 1] - s[i] >= f[max(0, q[tt] - 1)] - s[q[tt]]) tt--;

        // 3、i入队列
        q[++tt] = i;
    }
    // 输出结果
    cout << f[n] << endl;
    return 0;
}

6.2 KiB Raw Permalink Blame History Unescape Escape

AcWing 1087. 修剪草坪