题目链接：传送门

Description

There are N squares aligned in a row. The i-th square from the left contains an integer ai. Initially, all the squares are white. Snuke will perform the following operation some number of times: Select K consecutive squares. Then, paint all of them white, or paint all of them black. Here, the colors of the squares are overwritten. After Snuke finishes performing the operation, the score will be calculated as the sum of the integers contained in the black squares. Find the maximum possible score.、

Input

The input is given from Standard Input in the following format:

N K a1 a2... aN

Output

Print the maximum possible score.

Sample Input

10 5 5 -4 -5 -8 -4 7 2 -4 0 7

Sample Output

17

Solution

开始看错题了，以为是把颜色翻转，还感觉这道题特别难。。。 我们可以发现如果将一段长度为K的相同颜色的区间看作中转站的话，那么其他的点一定都能够取到。 然后枚举一下这些区间，维护一下所有数的前缀和和所有正数的前缀和，取个max即可

Code

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
27
28
29
30
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxn = 100000 + 100;
LL A[Maxn], Sum1[Maxn], Sum2[Maxn];
LL N, K;
int main()
{
#ifdef hk_cnyali
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
#endif
    scanf("%lld%lld", &N, &K);
    for (LL i = 1; i <= N; ++i)
    {
        scanf("%lld", &A[i]);
        Sum1[i] = Sum1[i - 1] + A[i];
        if (A[i] > 0) Sum2[i] = Sum2[i - 1] + A[i];
        else Sum2[i] = Sum2[i - 1];
    }
    LL Ans = 0ll;
    for (LL i = 1; i + K - 1 <= N; ++i)
    {
        LL Sum = Sum2[N] - (Sum2[i + K - 1] - Sum2[i - 1]);
        if (Sum1[i + K - 1] - Sum1[i - 1] > 0) Sum += Sum1[i + K - 1] - Sum1[i - 1];
        Ans = max(Ans, Sum);
    }
    cout<<Ans<<endl;
    return 0;
}