题解-luogu-p2627修剪草坪

题目链接

读入$n$个整数，选取其中若干个数，最多连续取$k$个，求取到数字和的最大值

$1\le k \le n \le 100000$

感谢@oy 的贡献

一道单调队列入门题。

面对动规题，首先设计状态转移方程。令$f[i]$表示$1-i$中连取不超过$K$个数，且第$i$个数不取所能累加的最大和。

因为第$i$个数不取，所以在$i$之前一定连取了一段数。这段数的长度可能为$0-K$（注意是$0-K$而不是$1-K$，可以通过手推样例发现最优解中可能存在连着两个数不取的情况）。连取的一段数所能累加的和可以用前缀和计算。考虑边界条件后，状态转移方程如下：

$$
f[i]=\max_{i-K-1\le j \le i-1} \lbrace f[j]+s[i-1]-s[j] \rbrace
$$

由于$max$函数的循环变量是$j$，所以只与$i$相关的变量$s[i-1]$可以作为常数提出到$max$函数之外，即：

$$
f[i]=\max_{i-K-1\le j \le i-1}\lbrace f[j]-s[j]\rbrace +s[i-1]
$$

将状态转移方程化简到这样，就已经可以用单调队列进行优化了。我们可以用单调队列维护$f[j]-s[j]$的最值，在循环时将其最大值取出再加上$s[i-1]$即为$f[i]$。

如果想不到该如何操作，也可以这样理解：

$$
g[i]=f[i]-s[i]
$$
$$
f[i]=\max_{i-K-1\le j \le i-1}\lbrace g[j]\rbrace+s[i-1]
$$

由于我们定义$f[i]$是第$i$个数不取的最优解，可以强行求解$f[N+1]$（虽然它似乎没有实际意义）作为本题的最终答案。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K;
ll s[100005], f[100005];
int q[100005];

int main() {
    scanf("%d%d", &N, &K);
    for (register int i = 1; i <= N; ++i) {
        scanf("%lld", &s[i]);
        s[i] += s[i-1];
    }
    int l = 0, r = 1;
    q[0] = 0, f[0] = 0;
    for (register int i = 1; i <= N + 1; ++i) {
        while (l < r && q[l] < i - K - 1) l++;
        f[i] = f[q[l]] - s[q[l]] + s[i-1];
        while (l < r && f[q[r - 1]] - s[q[r - 1]] < f[i] - s[i]) r--;
        q[r++] = i;
    }
    printf("%lld", f[N + 1]);
    return 0;
}