每日一题Mar27th 数学考试

题目链接
涉及算法：动态规划
不妨设,表示以为第二个区间开头的，最大可以获得的分数值。
于是有转移方程，
观察中的部分，实际是要求在范围内的最大的，直接在转移过程中更新即可。单组数据的时间复杂度为，于是整体的时间复杂度为，可以通过本题。
代码：没什么可说的，边界注意一下即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[400001],sum[400001],a[400001];
signed main (){
    int T;
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--){
        memset(f, 0, sizeof(f));
        memset(sum, 0, sizeof(sum));
        memset(a, 0, sizeof(a));
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = n; i >= 1; i--)
            sum[i] = sum[i + 1] - a[i + k] + a[i];//倒序处理出sum[]
        int Max = sum[1];
        for (int i = k + 1; i + k - 1 <= n; i++)
            f[i] = Max + sum[i], Max = max(Max, sum[i - k + 1]);
        Max = f[k + 1];
        for (int i = k + 2; i + k - 1 <= n; i++)
            Max = max(Max, f[i]);
        cout << Max << endl;
    }
    return 0;
}