NC 15553. 数学考试

发表于 分类于

链接

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

题意

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

思路

预处理前缀和 $s$

记 $f[i]$ 为前 $i$ 个元素中长度为 $k$ 的区间和的最大值：$f[i]=max(f[i-1],s[i]-s[i-k])(i>=k)$

最后枚举第二个区间的右端点求出最大值：$res=max(res,f[i-k]+s[i]-s[i-k])(i \ge 2k)$

代码

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;
}