牛客-https://www.nowcoder.com/acm/contest/96/H

链接：https://www.nowcoder.com/acm/contest/96/H
来源：牛客网

题目描述

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，
他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

输入描述:

第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）

输出描述:

输出一个整数，qwb能获得的最大分数

输入例子:

2

6 3

1 1 1 1 1 1

8 2

-1 0 2 -1 -1 2 3 -1

输出例子:

6

7

-->

示例1

输入

2

6 3

1 1 1 1 1 1

8 2

-1 0 2 -1 -1 2 3 -1

输出

6

7

  dp预处理出来f1,f2数组，f1[i]表示a[1..i]中长度为k的最大值，f2[i]表示a[i..n]中长度为k的最大值。然后枚举中间点得到最大值。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<cmath>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<vector>

 #include<functional>

 using namespace std;

 #define LL long long

 #define pii pair<long long ,int>

 #define mp make_pair

 #define inf 0x3f3f3f3f

 #define linf 0xffffffffff

 LL a[],pre[],f1[],f2[];

 int main()

 {

     //cout<<linf<<endl;

     int n,m,i,j,k,t;

     cin>>t;

     while(t--){

         cin>>n>>k;

         for(i=;i<=n;++i) scanf("%lld",a+i),pre[i]=pre[i-]+a[i],f1[i]=f2[i]=-linf;

     //    memset(f1,-inf,sizeof(f1));

     //    memset(f2,-inf,sizeof(f2));

         for(i=k;i<=n;++i){

             f1[i]=max(f1[i-],pre[i]-pre[i-k]);

         }

         for(i=n-k+;i>=;--i){

             f2[i]=max(f2[i+],pre[i+k-]-pre[i-]);

         }

         LL ans=-linf;

         for(i=k;i<n-k+;++i){

             ans=max(ans,f1[i]+f2[i+]);

         }

         cout<<ans<<endl;

     }

     return ;

 }