本文共 682 字，大约阅读时间需要 2 分钟。
题意：一套试卷有n道题，第i道题能获得的分数为a[i],选两个不连续的长度为k的区间（即[L,L+1,L+2,…,L+k-1]，[R,R+1,R+2,…,R+k-1]（R >= L+k）），使最终获得的分数最大。 题解：求前缀和来通过端点求这个区间内的和。又因为两个区间不能相交，维护i之前的连续k个数和的最大值maxx1，找到i之后连续k个数的和与maxx1相加使得maxx2最大 代码：
#includeusing namespace std;typedef long long ll;ll sum[2000010],a[2000010];int main(){ int t,n,k,flag; ll maxx1,maxx2,temp; cin>>t; while(t--){ cin>>n>>k; maxx1=-1e18,maxx2=-1e18; memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } maxx1=sum[k]-sum[0]; maxx2=sum[2*k]-sum[0]; for(int i=k;i<=n-k;i++){ maxx1=max(maxx1,sum[i]-sum[i-k]); maxx2=max(maxx2,maxx1+sum[i+k]-sum[i]); } cout< <
涉及知识点：前缀和
转载地址：http://ipnki.baihongyu.com/