题解 | #数学考试#

看到这个题先想到的是st表，后来发现用st表写内存超限了，才去想dp（还参考了别人的代码，我是dp弱子） st表的思路：（随便看看）求当前这个数字往后推k个的和，然后把这个值用数组存起来，暴力走一遍所有元素，ans=当前元素的值加上之后的元素中的最大值，于是想到最大值可以用st表维护，上代码（ac百分之50） 佬也可以浇浇窝怎么优化内存

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-x)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll a[200005]={0};
ll b[200005]={0};
ll dp[200005][33]={0};
vector<ll>arr;
void init_st(){
    for(int i=1;i<arr.size();i++) dp[i][0]=arr[i];
    int p=log2(arr.size()-1);
    for(int k=1;k<=p;k++){
        for(int s=1;s+(1<<k)<=arr.size();s++){
            dp[s][k]=max(dp[s][k-1],dp[s+(1<<(k-1))][k-1]);
        }
    }
    return;
}//st表初始化
ll st_query(int L,int R){
    int k=log2(R-L+1);
    ll ans=max(dp[L][k],dp[R-(1<<k)+1][k]);
    return ans;
}
void solve(){
    arr.clear();
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        b[i]=b[i-1]+a[i];
    }//求前缀和
    arr.resize(n-k+2);
    for(int i=1;i<=n-k+1;i++) arr[i]=b[i+k-1]-b[i-1];//当前元素往后推k位的和作为arr的元素值
    init_st();
    ll ans=-INF;
    for(int i=1;i+k<=n-k+1;i++){
        ll sum=0;
        sum+=arr[i];
        ll sum1=st_query(i+k,n-k+1);//之后的最大值
        sum+=sum1;
        ans=ans>sum?ans:sum;//更新答案
    }
    cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

然后是dp，别的博客写的都很好（让我刚学dp的蒟蒻也能看懂,因为借鉴了别人的的代码，就不放了）