NC 15553. 数学考试

链接

https://ac.nowcoder.com/acm/problem/15553

题意

在长度为 n 的序列中,选两个无交集的长度为 k 的区间,使可以选择的两个区间和的最大值

思路

预处理前缀和 s

f[i] 为前 i 个元素中长度为 k 的区间和的最大值:f[i]=max(f[i1],s[i]s[ik])(i>=k)

最后枚举第二个区间的右端点求出最大值:res=max(res,f[ik]+s[i]s[ik])(i2k)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll s[N],f[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--) {
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) {
ll t;
cin>>t;
s[i]=s[i-1]+t;
}
memset(f,-0x3f,sizeof f);
ll res=-0x3f3f3f3f3f3f3f3f;
for(int i=k;i<=n;i++) f[i]=max(f[i-1],s[i]-s[i-k]);
for(int i=2*k;i<=n;i++) res=max(res,f[i-k]+s[i]-s[i-k]);
cout<<res<<endl;
}
return 0;
}