题目描述
n个数字,每个数字有一个标记 0
or
1 , 我们可以把某一段连续k个数字的标记全部变为1, 求变完以后的数组中 标记为1的所有数字的和0为不可以被选中,1 是可以被选中
分析
先求处没有变完之前所有标记为1的数字的和ans
,然后用一个前缀和数组将标记为0的数字的和预处理出来,最后求出所有长度为k的连续数字中 标记为0的数字的和的最大值res
, 最终结果即为ans + res
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <vector>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n + 1), sum(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
int x, ans = 0;
for(int i = 1; i <= n; i ++ ) { // 更新 ans 以及 求前缀和
cin >> x;
sum[i] = sum[i - 1]; // 更新前缀和数组
if(!x) sum[i] += a[i]; // 如果标记为0 那么就加进前缀和数组
else ans += a[i]; // 否则更新ans
}
int res = 0;
for(int i = 1; i <= n - k + 1; i ++ ) {
int s = i + k ;
res = max(res, sum[s - 1] - sum[i - 1]); // 利用前缀和求出最大值
}
cout << res + ans; // 输出结果
return 0;
}