AcWing 3493. 最大的和
原题链接
简单
作者:
ShineWine
,
2021-05-11 19:36:54
,
所有人可见
,
阅读 240
题目描述
给定一个长度为 n 的正整数数列 a1,a2,…,an。
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
样例
输入:
3 1
2 5 4
0 0 1
输出:
9
前缀和预处理
1. 我们将两个输入数组的原状态和全选状态预处理出两个前缀和数组
2. 然后枚举每一个遍历到的窗口,滑动窗口进行求解
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
int n,k;
const int N = 1000010;
int w[N];
int st[N];
ULL s1[N]; // 注意数据范围 前缀和有可能爆int
ULL s2[N];
int main()
{
cin >> n >> k;
for(int i = 1; i <=n;i++) cin >> w[i];
for(int i = 1; i <=n ;i++)
{
int x;
cin >> x;
if(x == 1) st[i] = w[i];
}
//预处理两个前缀和
for(int i = 1; i<=n;i++) s1[i] = s1[i-1] + w[i];
for(int i= 1; i <= n; i++) s2[i] = s2[i-1] + st[i];
// 枚举所有窗口
ULL res = 0;
for(int i = 0,j = k; j<=n;i++,j++)
{
res = max(res,(s1[j]-s1[i]+ s2[n]-s2[j] + s2[i] - s2[0]));
}
cout <<res;
return 0;
}