题目描述
给定一个长度为 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
前缀和$o(n)$
要让一段区间内变化后总和最大,就需要让长度为k的区间内总和的差距最大,通过前缀和技巧预处理数组,得到总和
两次前缀和
第一次将所有的数据都加入到前缀和数组bb中,第二次只将状态可选的数据加入到前缀和数组aa中
再遍历一次数组,通过res变量记录将数组bb中长度为k的区间和减去数组aa中长度为k的区间和的最大值,取$MAX$
最后将所有区间和加上res即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,k;
ll a[N],b[N],aa[N],bb[N];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
if(b[i]==1){
aa[i]=aa[i-1]+a[i];
}else{
aa[i]=aa[i-1];
}
bb[i]=bb[i-1]+a[i];
}
ll res=0;
for(int i=k;i<=n;i++){
res=max(res,bb[i]-bb[i-k]-aa[i]+aa[i-k]);
}
cout<<res+aa[n];
return 0;
}
前缀和是给大佬玩明白了奥 orz
光头哥,光头哥
大佬, 最后从k到n的那个循环怎么理解啊
从第k个数开始 每次提取i-k到i区间的区间和
大佬,
第一次将所有的数据都加入到前缀和数组a中,第二次只将状态可选的数据加入到前缀和数组b中
这句话看代码是 bb数组装所有数据,aa数组装可选数据
是这样的吗?
对的
已更正 谢谢提醒
我去,66666啊,前缀和还能这样用,orz!!!!!!!!!!!
哇 好快 很厉害