题意

有 个数选两个长度为 的不相交区间，使得他们的和尽量大，求最大和。

分析

我们可以固定一个区间，然后来找另一个区间。
记 为 的前缀和
在这道题中，我们枚举 ，然后固定右边的区间 ，右边的贡献为
那么，现在就是在 中找长度为 的连续区间的和的最小值。
那么我们设 表示 中长度为 的连续区间的和的最小值，考虑第 个点作为右端点，转移方程就是：
到这里这题就解决了。
我们枚举右边区间的左端点 ，然后 即可。
这个代码跑了108ms，牛客最快哦

代码如下

#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
LL s[N], f[N], ans;
int main(){
    int i, j, n, m, T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(i = 1; i <= n; i++) s[i] = s[i - 1] + read();
        f[m - 1] = ans = -1e18;
        for(i = m; i <= n - m; i++) f[i] = max(f[i - 1], s[i] - s[i - m]), ans = max(ans, s[i + m] - s[i] + f[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

下面说说我对思考题的想法

第一个

设 表示前 的最大子段和，表示 的最大子段和。求最大子段和是普及组题，这里略。那么

第二个

设 表示前 个数，分成 段长度为 的连续字段最大值。转移方程：

第三个

设 表示前 个数，分成 段，第 个不选/选的最大值，考虑第 个是否新开一段，转移方程：