AcWing 3493. 最大的和 带注释
原题链接
简单
作者:
蓬蒿人
,
2021-05-11 20:34:20
,
所有人可见
,
阅读 360
本题前置知识 前缀和
#include <iostream>
using namespace std;
//本题可以转换为求 初始未选中元素和最大的区间 区间长度为k
//最后 初始未选中元素和最大的区间的和 加上所有初始选中的元素之和就是答案
int a[100010],n,k,bs[100010];
long long s[100010];
//看到1e5数据范围要警惕 算算要不要开long long
int main()
{
scanf ("%d%d",&n,&k);
int l,r;
long long res=0;
//看到1e5数据范围要警惕 算算要不要开long long
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
long long x2=0;
//x2存所有初始选中的数值之和
for (int i=1;i<=n;i++) {
scanf ("%d",&bs[i]);
if (bs[i]) {
x2+=a[i];
a[i]=0;
}
s[i]=s[i-1]+a[i];
//我们的s前缀和数组只加入初始未被选中的
//初始选中的我们将其视作0
if (i-k>=0&&res<s[i]-s[i-k]){
l=i-k,r=i;
res=s[i]-s[i-k];
//lr存最大和区间的左右下标 记得更新res
}
}
cout<<s[r]-s[l]+x2;
//最后 初始未选中元素和最大的区间的和 加上所有初始选中的元素之和就是答案
return 0;
}
捉蓬蒿