[NC15553] 数学考试

1
2
3
时间限制：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）。

输入描述

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

输出描述

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

输入

1
2
3
4
5
2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

输出

1
2
6
7

题解

题目解析

这道题是一个区间dp+前缀和的题目,按理说应该挺简单的= =.但是我还是卡了好长时间.

这道题的做法是 $O(n)$ 方法.用一个res1变量始终维护全部左侧长度为k的区间最大值.然后依次一个一个遍历右侧所有长度为k的区间就好了.因为我们已经维护左侧所有长度为k的最大值了,res2就可以维护以移动指针i到i+k区间与i左边所有区间的最大值就好了,然后i从k->n-k遍历一遍就得到答案了.

AC代码

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 <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 200010;

ll dp[MAXN],sum[MAXN],res1,res2;
int T,n,k,temp;

signed main(){
    cin >> T;
    while(T--){
        cin >> n >> k;
        res1 = res2 = -1e18;//这里的数据出的有点刁钻
        for(int i=1;i<=n;i++){
            cin >> temp;
            sum[i] = sum[i-1] + temp;
        }
        for(int i=k;i<=n-k;i++){
            res1 = max(res1,sum[i]-sum[i-k]);//维护i左侧所有可能的最大值
            res2 = max(res2,res1+sum[i+k]-sum[i]);//依次遍历
        }
        cout << res2 << endl;
    }
    return 0;
}