题目描述

给定一个长度为 n 的正整数数列 a1,a2,…,an。

初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。

你可以选择一个长度恰好为 k 的区间 [i,i+k−1]，使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。

请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。

输出格式
一行一个整数，表示答案。

数据范围
对于 30% 的数据，1≤k≤n≤1000
对于 100% 的数据，1≤k≤n≤105,1≤ai≤105

样例

输入样例:

3 1
2 5 4
0 0 1

输出样例:

9

算法1

时间复杂度 $O(N)$

用一个队列来维护长度为m的滑动窗口,维护窗口内的不可选的数的和 当长度大于m时从队列里弹出一个,如果弹出的数是可选的则不管,如果弹出的数是不可选,则减去弹出的数.更新最大的不可选数.
最后最大不可选数和所有可选数相加可以得到答案
sum 是所有可选数的和
ans 是长度为k的滑动窗口的最大的不可选数和
max_t 是当前窗口内的不可选数的和
注意 答案爆int

C++ 代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

long long q[N], st[N];
long long sum, max_t, ans;
queue<int> my_q;

int main(void) {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &q[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &st[i]);
    for (int i = 1; i <= n; i++) {
        if (st[i] == 1) sum += q[i];
        else max_t += q[i];
        my_q.push(q[i]);
        if (my_q.size() > m) {
            auto t = my_q.front();
            if (!st[i - m]) max_t -= t;
            my_q.pop();
        }
        ans = max(ans, max_t);
    }

    cout << ans + sum << endl;
}