给定一个长度为 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
思路
计算全部可选的和,同时建立不可选元素的前缀和,之后枚举k长度区间求最值即可.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll a[N],s[N];
ll st[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i = 1; i <= n; ++ i){
scanf("%d",&a[i]);
}
ll sum = 0;//防止爆掉
for(int i = 1; i <= n; ++ i ){
cin>>st[i];
if(st[i] == 1){
s[i] = s[i-1];//可选维护前缀
sum += a[i];
}else{
s[i] = s[i-1] + a[i];//不可选,增加值,维护前缀
}
}
ll res = 0;
for(int i = k ; i <= n; ++ i){
res = max(res,s[i]-s[i-k]);//计算长度为k区间的最值
}
cout<<res+sum;
return 0;
}