3.27 数学考试

在这题我们要选择两个区间 首先我们知道 右区间一定在左区间右边
于是 我们枚举i作为分界线 i左边最大的长度为k的的区间 i右边最大的长度为k的的区间
解题的思路出来了 那么该如何用程序表达
用cnt数组表示前缀和
那么i左边的最大区间和表达为 dp1[i]=max(dp1[i-1],cnt[i]-cnt[i-k]);
那么i右边的最大区间和表达为 dp2[i]=max(dp2[i+1],cnt[i+k-1]-cnt[i-1]);
答案就为 ans=max(ans,dp1[i]+dp2[i+1]);
PS：记得将dp1 dp2 ans 都初始化为负无穷大

#include <bits/stdc++.h>
#define ll long long
ll const N=2e5+5;
ll const INF=1e18;
using namespace std;
ll t,n,k,a[N],cnt[N],dp1[N],dp2[N];
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        memset(dp1,-0x7f,sizeof(dp1));
        memset(dp2,-0x7f,sizeof(dp2));
        scanf("%lld %lld",&n,&k);
        cnt[0]=0;
        for(int i=1;i<=n;++i){scanf("%lld",&a[i]);cnt[i]=cnt[i-1]+a[i];}
        for(int i=k;i<=n-k;++i)   dp1[i]=max(dp1[i-1],cnt[i]-cnt[i-k]);
        for(int i=n-k+1;i>=k+1;--i)dp2[i]=max(dp2[i+1],cnt[i+k-1]-cnt[i-1]);
        ll ans=-INF;
        for(int i=k;i<=n-k;++i) ans=max(ans,dp1[i]+dp2[i+1]);
        cout<<ans<<endl;
    }
    return 0;
}