题目大意

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完， 他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间, 即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

分析与题解

很显然，这题是一个贪心的做法，如果我们从1-n枚举第一段的起点，设起点为s，那么只要找到以[s+k,n-k+1]（s+k>=n-k+1)中某个点为起点的最大连续k个的和。其中可以通过维护每个点开始的k个数的和以及后缀的k个数的和的最大值即可。
显然转移便是： ma[i] = max(s[i], ma[i+1]) 其中ma维护的就是i这个点以及该点以后的连续k段的和的最大值，s[i]是以i为起点的连续k个数的和。
答案便可以通过 ans = max(ans, s[i] + ma[i+k]) 更新得到。

代码

#include <bits/stdc++.h>
#define LL long long
#define rep(i,a,b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 2e5 + 50;
LL w[N], s[N], ma[N];
int T, n, k;

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n >> k;
        rep(i, 1, n) {
            cin >> w[i];
            s[i] = 0;
        }

        memset(ma, -0x3f3f3f, sizeof ma);

        LL pre = 0, idx = 0;
        rep(i, 1, n) {
            pre += w[i];
            if(i == k) s[ ++ idx] = pre;
            else if(i > k) s[++ idx] = s[idx - 1] + w[i] - w[idx - 1];
        }

        ma[n - k + 1] = s[n - k + 1];
        for(int i = n - k ; i >= 1; i --)
        {
            ma[i] = max(s[i], ma[i + 1]);
        }

        LL res = s[1] + ma[1 + k];
        for (int i = 2; i <= n - 2 * k + 1; i ++)
        {
            res = max(s[i] + ma[i + k], res);
        }

        cout << res << endl;
    }
}