链接
https://ac.nowcoder.com/acm/problem/15553
题意
在长度为 的序列中,选两个无交集的长度为 的区间,使可以选择的两个区间和的最大值
思路
预处理前缀和
记 为前 个元素中长度为 的区间和的最大值:
最后枚举第二个区间的右端点求出最大值:
代码
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; }
|
来做第一个留言的人吧!