【每日一题】数学考试 (前缀和+dp)

Solution
鬼鬼，鬼知道我这道题做了多少次，一直卡在83，今天才发现ans的初始值没处理好，一开始ans初始化为0一直过不去，这么多天终于过了。
取区间里两段长度为k的子区间使和最大，肯定是dp。
设pre[i]前i个数的长度为k的区间的最大和，那么只要遍历的时候再加上i-k的另一段k区间就可以了。

Code

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}

const int manx=3e5+5;

ll pre[manx],s[manx];

int main(){
    ll p=read();
    while(p--){
        ll n=read(),k=read();
        for(int i=1;i<=n;i++) pre[i]=-1e18;
        for(int i=1;i<=n;i++)
            s[i]=s[i-1]+read();
        ll ans=-1e18;
        for(int i=k;i<=n;i++){
            pre[i]=max(pre[i-1],s[i]-s[i-k]);
            if(i>=2*k) ans=max(ans,s[i]-s[i-k]+pre[i-k]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}