题目描述
给定一个长度为 n 的正整数数列 a1,a2,…,an。
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
算法1
(前缀和 + 枚举) $O(n)$
我们称对应位置为1的是可选数,对应位置为0的数为不可选数。由于一次操作之后长度为k的区间内所有数都会成为可选数,因此可以贪心的先把可选数求和,再单独对不可选数作前缀和,枚举长度为k的区间求其最大区间和。那么我们能选的元素之和就是原来就可选的数+变为可选的数之和。
时间复杂度
$O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, k;
int a[N], b[N];
int sum[N];
signed main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// cout << setiosflags(ios::fixed) << setprecision(2);
// cout << setw(2) << setfill('0');
cin >> n >> k;
for (int i= 1; i <= n; ++i) {
cin >> a[i];
}
for (int i= 1; i <= n; ++i) {
cin >> b[i];
}
int toadd = 0;
for (int i = 1; i <= n; ++i) {
if (!b[i]) {
sum[i] = sum[i-1] + a[i];
}
else {
sum[i] = sum[i-1];
toadd += a[i];
}
}
auto getsum = [&](int l, int r) {
return sum[r] - sum[l-1];
};
int ret = 0;
for (int l = 1; l <= n; ++l) {
int r = min(l + k - 1, n);
ret = max(ret, getsum(l, r));
}
cout << ret + toadd<< "\n";
return 0;
}
大佬,可以解释下
auto getsum = & {
return sum[r] - sum[l-1];
};
这几行代码的作用吗?
定义匿名函数。这里getsum当作函数来使用
哦哦,我去搜索学习下,谢谢佬