题目分析

可将本题转换为在一个数组中选出一些元素，保证所选的元素中连续元素长度不能超过 $m$，使得最终选出元素的权值最大。

暴力枚举

枚举每个元素 选/不选，对枚举出来的每个方案判断是否有连续的 $m$ 个元素，如果不存在连续的 $m$ 个元素，并维护选出合法方案中元素的最大权值和。

这样枚举的时间复杂度为 $O(2^n)，显然是不满足要求的。

优化冗余的计算

分析上面暴力枚举的方式，是以全局的思想来计算的，即先枚举出在所有数中合法的方案，然后再维护最大权值。并不是从 局部 的思想将问题拆分，导致无法分离出子问题。暴力枚举方式之所以会有很多冗余的计算，就是因为存在好多相同子问题的重复计算。

假设要在前 $i$ 个位置中选出若干元素，且满足不存在长度超过 $m$ 的连续元素。对于前 $i$ 个位置来说，若只看 选\不选 元素 $i$ 时：

• 不选元素 $i$
  • 第 $i$ 个元素的选择不影响前面的选择，此时的最大元素应该等于在前 $i-1$ 个位置选出长度不超过 $m$ 的连续序列的结果。
• 选元素 $i$
  • 对于元素 $i$ 来说，一定属于最后一个连续的元素序列，且最后这个序列的长度是意是不可超过 $m$ 的。即最后一个连续区间的起点为 $[i-m+1, i]$ 中的一个数 $k$，起点 $k$ 到 $i$ 的元素和 + 在前 $k-2$ 个元素中的选出连续子序列的长度不超过 $m$ 的最大子序列和。

这样在求选元素 $i$ 时的最大子序列时，可将问题转换为求在前 $k（i - m - 1 \le k < i）$ 个元素中的选出连续子序列的长度不超过 $m$ 的最大子序列和。

方法一

根据以上的分析可以该问题抽象为一个状态机模型。

状态机表示

可对每个位置都抽象出 $2$ 个状态：选 $1$ /不选 $0$。

再根据子问题的转换可以做如下的状态设计：

• f[i][0] 表示在前 $i$ 个元素中不选元素 $i$ 可得到的最长连续元素长度小于等于 $m$ 的最大子序列和；
• f[i][1] 表示在前 $i$ 个元素中且选元素 $i$ 可得到的最长连续元素长度小于等于 $m$ 的最大子序列和；

状态转移

f[i][0] = max(f[i - 1][0], f[i - 1][1])，

f[i][1] = max(f[k][0] + s[i] - s[k])，其中 $i - m \le k < i$。

这样在计算 f[i][1] 的时候只需遍历前 $m$ 个元素的状态 $0$ 即可。

时间复杂度为 $O(n \times m)$。还是不能满足要求，但相较于暴力方式已经优化了非常大的时间了。

发现性质，使用单调队列

f[i][1] = max(f[k][0] + s[i] - s[k])，其中 $i - m \le k < i$。

观察上面这个公式，$i$ 前面每个位置 $k$ 的权值之间不单单与 $f[k][0]$ 有关，还和它们之间相差的元素和有关。但这并不影响是在 $i$ 前面长度为 $m$ 的区间中找到 f[k][0] + s[i] - s[k] 的最大值。

如果要使单调队列满足上述条件，那么只需在将 f[i][0] 入队时与队尾的 f[k][0] + s[i] - s[k] 作为比较条件即可。

代码实现

初始时将 f 数组全置为 $0$ 即可。

最终输出 max(f[n][0], f[n][1]) 即可。

代码模板如下：

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;
LL f[N][2];
LL s[N];
int q[N];
int n, m;

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

    int hh = 0, tt = -1;
    q[++ tt] = 0;

    for(int i = 1; i <= n; i ++) {
        if(i - q[hh] > m) hh ++;
        f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        f[i][1] = f[q[hh]][0] + s[i] - s[q[hh]];
        while(hh <= tt && f[q[tt]][0] + s[i] - s[q[tt]] < f[i][0]) tt --;
        q[++ tt] = i;
    }
    cout << max(f[n][0], f[n][1]) << endl;

    return 0;
}

时间复杂度为 $O(n)$。

方法二（Y 神法）

观察上述方法，f[k][0] 的作用只是为了在计算后面某个位置的状态 $1$ 时，使用 s[i] - s[k] 表示最后一个区间为 $[k+1,i]$，那就一定不能选元素 $k$，即对应 f[k][0]。

所以可只用一维数组 f[i] 来表示在前 $i$ 个元素选出的所有合法子序列中连续元素长度不超过 $m$ 的子序列的最大和。

• 不选元素 $i$ 时，最大的结果为 f[n-1]
• 选元素 $i$ 时
  假设最后这个区间的起点为 $k$，元素 $k - 1$ 一定不能选。即在前 $k - 2$ 个元素中选出的所有合法子序列中连续元素长度不超过 $m$ 的子序列的最大和。

状态转移公式：
f[i] = max(f[i - 1], f[k - 1] + s[i] - s[k])，其中 $max(0,i - m) \le k < i$。

即在 $i$ 前面长度不超过 $m$ 的区间中选出 f[k - 1] + s[i] - s[k] 最大的 $k$ 值。由于 $s[i]$ 时固定的，所以只需维护 f[k-1] - s[k] 的值即可。

但是会出现 $k-1=-1$ 的情况，但是不能影响最后的结果，这种情况只需返回 $0$ 即可。

代码实现

初始时，f 数组均为 $0$。

最终输出 f[n] 即可。

代码模板如下：

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;
LL s[N];
LL f[N];
int q[N];
int n, m;

LL get(int i) {
    return f[i - 1] - s[i];
}

int main() {
    cin >> n >> m;

    for(int i = 1; i <= n; i ++) scanf("%lld", &s[i]), s[i] += s[i - 1];

    int hh = 0, tt = -1;
    q[++ tt] = 0;
    for(int i = 1; i <= n; i ++) {
        if(i - q[hh] > m) hh ++;

        f[i] = max(f[i - 1], s[i] + get(q[hh]));
        while(hh <= tt && get(q[tt]) < get(i)) tt --;
        q[++ tt] = i;
    }
    cout << f[n] << endl;

    return 0;
}

时间复杂度为 $O(n)$。