2018年长沙理工大学第十三届程序设计竞赛 H数学考试

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

数学考试

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

今天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

从前往后，用尺取法取k个，存下最大值，不断更新

从后往前，用尺取法取k个，存下最大值，不断更新

最后遍历一遍，求前一段+后一段的和最大

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int maxn=;

 ll a[maxn],sum1[maxn],sum2[maxn],dp1[maxn],dp2[maxn];

 int main()

 {

     int T;scanf("%d",&T);

     while(T--)

     {

         int n,k;scanf("%d%d",&n,&k);

         for(int i=;i<=n+;i++)

             dp1[i]=dp2[i]=-1e18;

         sum1[]=sum2[n+]=;

         for(int i=;i<=n;i++)

         {

             scanf("%lld",&a[i]);

             sum1[i]=sum1[i-]+a[i];

             if(i>k)sum1[i]-=a[i-k];

             if(i==k)dp1[i]=sum1[i];

             else dp1[i]=max(sum1[i],dp1[i-]);

         }

         for(int i=n;i>=;i--)

         {

             sum2[i]=sum2[i+]+a[i];

             if(n-i>=k)sum2[i]-=a[i+k];

             if(n-i<k)dp2[i]=sum2[i];

             else dp2[i]=max(dp2[i+],sum2[i]);

         }

         ll ma=-1e18;

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

             ma=max(dp1[i]+dp2[i+],ma);

         printf("%lld\n",ma);

     }

     return ;

 }

秒客网