算法1
(前缀和+滑动窗口) $O(n)$
记得开longlong 不然会爆掉噢
时间复杂度
O (n)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N= 1100000;
typedef long long ll;
ll a[N];
ll s[N];
ll ans;
int n,k;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int state=0;
for(int i=1;i<=n;i++)
{
//如果当前位是可选的: 也就是1
// 则直接选择它,将它加入结果ans,并将原数置为0
// (因为我们前缀和操作只处理不可选的)
cin>>state;
if(state)
{
ans+=a[i];
a[i] = 0;
}
s[i] = s[i-1]+a[i];
}
ll res = 0;
// 枚举每一个滑动窗口左端点即可
for(int i=1;i<=n;i++)
{
int r = i+k-1;
if(r>n) r=n;
ll now = s[r]-s[i-1];
if(now>res) res = now;
}
cout<<ans+res;
return 0;
}
# 还是这个比较容易理解= =