题目描述
给定一个长度为 n 的正整数数列 a1,a2,…,an。
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数 ai。
第三行包含一个长度为 n 的 01 序列,如果第 i 个数为 1,表示 ai 的初始状态为可选,如果第 i 个数为 0,表示 ai 的初始状态为不可选。
输出格式
一行一个整数,表示答案。
数据范围
对于 30% 的数据,1≤k≤n≤1000
对于 100% 的数据,1≤k≤n≤105,1≤ai≤105
样例
输入样例1:
3 1
2 5 4
0 0 1
输出样例1:
9
输入样例2:
4 3
10 5 4 7
0 1 1 0
输出样例2:
19
算法1
(滑动窗口) $O()$
时间复杂度
参考文献
Python3 代码
[n, k] = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
state = [int(x) for x in input().split()]
asum = 0
for i in range(n):
if state[i] == 1:
asum += nums[i]
R = 0
winadd = 0
while R < k:
if state[R] == 0:
winadd += nums[R]
R += 1
max_winadd = winadd
while R < n:
if state[R] == 0:
winadd += nums[R]
L = R - k
if state[L] == 0:
winadd -= nums[L]
max_winadd = max(max_winadd, winadd)
R += 1
res = asum + max_winadd
print(res)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
int k; cin >> k;
vector<int> nums(n);
for (int i = 0; i < n; i ++) cin >> nums[i];
vector<int> state(n);
for (int i = 0; i < n; i ++) cin >> state[i];
long long asum = 0;
for (int i = 0; i < n; i ++)
if (state[i] == 1)
asum += nums[i];
int R = 0;
long long winadd = 0;
while (R < k)
{
if (state[R] == 0)
winadd += nums[R];
R ++;
}
long long max_winadd = winadd;
while(R < n)
{
if (state[R] == 0)
winadd += nums[R];
int L = R - k;
if (state[L] == 0)
winadd -= nums[L];
max_winadd = max(max_winadd, winadd);
R ++;
}
long long res = asum + max_winadd;
cout << res << endl;
return 0;
}
算法2
(前缀和) $O()$
state为0的数的前缀和
时间复杂度
参考文献
python3 代码
[n, k] = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
state = [int(x) for x in input().split()]
presum_0 = [0 for _ in range(n + 1)]
asum = 0
for i in range(n):
if state[i] == 1:
asum += nums[i]
presum_0[i+1] = presum_0[i]
else:
presum_0[i+1] = presum_0[i] + nums[i]
max_window_0 = presum_0[k]
for i in range(k, n):
cur_window_0 = presum_0[i+1] - presum_0[i+1-k]
max_window_0 = max(max_window_0, cur_window_0)
res = asum + max_window_0
print(res)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
int k; cin >> k;
vector<int> nums(n);
for (int i = 0; i < n; i ++) cin >> nums[i];
vector<int> state(n);
for (int i = 0; i < n; i ++) cin >> state[i];
long long asum = 0;
vector<long long> presum_0(n + 1, 0);
for (int i = 0; i < n; i ++)
{
if(state[i] == 1)
{
presum_0[i+1] = presum_0[i];
asum += nums[i];
}
else
presum_0[i+1] = presum_0[i] + nums[i];
}
long long max_window_0 = presum_0[k];
for (int i = k; i < n; i ++)
{
long long cur_window_0 = presum_0[i + 1] - presum_0[i + 1 - k];
max_window_0 = max(max_window_0, cur_window_0);
}
long long res = asum + max_window_0;
cout << res << endl;
return 0;
}