前缀和求解
$我们可以先把可选的数的总和求出来。$
$之后再用一个数组处理出不可选的数组的前缀和$
$最后枚举即可,看长度为k的不可选的数的区间和,最大是多少。$
$最后加上原来可以选的数的总和即可$
时间复杂度O(n)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
int b[N];
int n,k;
ll sum;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]); //a数组原来存储每个数
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]); //b数组表示是否可选
}
for(int i=1;i<=n;i++)
if(b[i]==1) sum+=a[i]; //sum存原来所有可以选的数的总和
for(int i=1;i<=n;i++)
{
if(b[i]==0) a[i]=a[i-1]+a[i]; //a数组存储不可选的前缀和
else a[i]=a[i-1];
}
ll res=0;
for(int i=1;i<=n-k+1;i++)
{
if(res<a[i+k-1]-a[i-1]) res=a[i+k-1]-a[i-1];//依次枚举长度为k的区间的总和,求最大即可
}
cout<<res+sum; //最后要加上原来可选的数的总和
return 0;
}
赞