暴力
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, k;
int a[N];
bool vis[N];
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for(int i = 0; i < n; i++) {
scanf("%d", &vis[i]);
}
// 最暴力的想法我们可以枚举每个k区间,求出目标和,取个max
int res = 0;
for(int i = 0; i+k-1 < n; i++) {
int sum = 0;
for(int j = 0; j < n; j++) {
if(vis[j] || j>=i&&j<=i+k-1) {
sum += a[j];
}
}
res = max(res, sum);
}
cout << res << endl;
return 0;
}
前缀和优化
使用2个前缀和数组,减少区间的重复计算
注意前缀和数据爆int
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
int n, k;
int a[N];
bool vis[N];//一般来说,bool和int选择int
LL s1[N];//所有数的前缀和
LL s2[N];//可选数的前缀和
LL old;
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s1[i] = s1[i-1]+a[i];
}
for(int i = 1; i <= n; i++) {
scanf("%d", &vis[i]);
s2[i] = s2[i-1];
if(vis[i]) {
old += a[i];
s2[i] += a[i];
}
}
// 最暴力的想法我们可以枚举每个k区间,求出目标和,取个max
// 前缀和?不太行,原本的和,区间和O(1) 重叠的部分:减去原区间和
LL res = 0;
for(int i = 1; i+k-1 <= n; i++) {
LL sum = 0;
int l = i, r = i+k-1;
sum = old+(s1[r]-s1[l-1])-(s2[r]-s2[l-1]);
// for(int j = 0; j < n; j++) {
// if(vis[j] || j>=i&&j<=i+k-1) {
// sum += a[j];
// }
// }
res = max(res, sum);
}
cout << res << endl;
return 0;
}