牛客竞赛每日一题3.27 数学考试 动态规划

https://blog.csdn.net/qq_43804974/article/details/105115539

虽然说是动态规划实则就是在暴力找答案。
我们答案要求的是两个区间，所以我们只要选取一个区间，然后枚举这个区间往前的所有区间能提供的最大答案就好了。
我们需要什么呢value[i] , 区间的最后位置是i，这个区间的权值总和.
这个value可以用前缀和轻松算。
下一个就是fmax[i],代表的是[1,i]这些位置能构成的最大区间权值然后答案明显就是

ans = max(ans, value[i] + fmax_[i - k]);

当我们写出value数组后就可以直接写出fmax数组了。
综上所述复杂度是O(N)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define int long long
#define double long double
using namespace std;
#define PI  3.1415926535898
#define eqs 1e-17
const long long max_ = 200000 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch<'0' || ch>'9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline int min(int a, int b) {
    return a < b ? a : b;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
int tree_[max_],value[max_],n,k,sum[max_],fmax_[max_];
signed main() {
    int T = read();
    while (T--){
        n = read(), k = read();
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; i++) {
            sum[i] = read();
            sum[i] += sum[i - 1];
        }
        memset(value, 128, sizeof(value));
        for (int i = 1 + k - 1; i <= n; i++) {
            //[i - k + 1,i]
            value[i] = sum[i] - sum[i - k];
        }
        fmax_[1] = value[1];
        for (int i = 2; i <= n; i++) {
            fmax_[i] = max(fmax_[i - 1], value[i]);
        }
        //value[i], 以i为结尾的权值
        int ans = -INF;
        for (int i = 2 * k; i <= n; i++) {
            //[i - k + 1,i]
            //[1,i - k]
            ans = max(ans, value[i] + fmax_[i - k]);
        }
        cout << ans << endl;
    }
    return 0;
}