最大的和
题目描述
给定一个长度为 $n$ 的正整数数列 $a_1,a_2,…,a_n$
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 kk 的区间$[i,i+k−1]$,使得 $a_i∼a_{i+k−1}$这 $k$个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
输入格式
第一行包含两个整数 $n$ 和 $k$。
第二行包含 $n$个整数 $a_i$。
第三行包含一个长度为 $n$ 的 $01$序列,如果第 $i$ 个数为 $1$,表示 $a_i$ 的初始状态为可选,如果第 $i$个数为 $0$,表示 $a_i$ 的初始状态为不可选。
输出格式
一行一个整数,表示答案。
数据范围
对于 $30\%$的数据,$1≤k≤n≤1000$
对于 $100\%$ 的数据,$1≤k≤n≤10^5$,$1≤a_i≤10^5$
输入样例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的元素添加到和中,然后遍历整个数组,如果当前元素不可选,则将他修改为可选加入到和中,然后判断如果当前已经超过窗口m的大小并且之前数不可选,就删除该数,然后取最大值
实现代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
LL sum = 0;
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i ++) scanf("%d",&b[i]);
for(int i = 1;i <= n;i ++) if(b[i]) sum += a[i];
LL res = 0;
for(int i = 1;i <= n;i ++)
{
if(!b[i]) sum += a[i];
if(i > m && !b[i - m]) sum -= a[i-m];
res = max(res,sum);
}
cout << res << endl;
return 0;
}