每日一题 3月27日 数学考试 线性DP

思路：很容易可以看出来是一个线性DP。

#include <bits/stdc++.h>
using namespace std;
#define LL long long

LL a[200005], f[200005];
int main(){

    int t; scanf("%d", &t);
    while(t--){
        int n, k; scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++){
            scanf("%lld", &a[i]);
            a[i]+=a[i-1];
            f[i]=-1ll<<60;
        }
        LL mx=-1ll<<60;
        for(int i=k; i<=n; i++){
            f[i]=max(f[i-1], (a[i]-a[i-k]));
            if(i>=2*k){
                mx=max(mx, (a[i]-a[i-k])+f[i-k]);
            }
        }
        printf("%lld\n", mx);
    }

    return 0;
}