题意:选2个不连续长度为K的区间和的最大值
思路:用sum[i]表示1到i区间中长度为K的最大值,然后从2k开始寻找2个区间长度为K和的最大值
#include <iostream> #include <algorithm> #include <cmath> #include <ctype.h> #include <cstring> #include <cstdio> #include <set> #include <sstream> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #define MAXX 100005 #define SIS std::ios::sync_with_stdio(false) #define ll long long //#include<bits/stdc++.h> using namespace std; const ll INF=1e12; const int MAX =1e6+5; const int mod=998244353; ll a[200005]; ll sum[200005]; int main() { SIS; int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { sum[i]=-INF; scanf("%lld",&a[i]); a[i]=a[i-1]+a[i]; if(i>=k) { sum[i]=max(sum[i-1],(a[i]-a[i-k])); } } ll ans=-INF; for(int i=2*k;i<=n;i++) { ans=max(ans,(a[i]-a[i-k])+sum[i-k]); } printf("%lld\n",ans); } return 0; }