AcWing 3493. 最大的和 - AcWing

题目描述

给定一个长度为 n 的正整数数列 a1,a2,…,an。

初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。

你可以选择一个长度恰好为 k 的区间 [i,i+k?1]，使得 ai～ai+k?1 这 k 个元素的状态全部变为可选。

请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数 ai。

第三行包含一个长度为 n 的 01 序列，如果第 i 个数为 1，表示 ai 的初始状态为可选，如果第 i 个数为 0，表示 ai 的初始状态为不可选。

输出格式

一行一个整数，表示答案。

数据范围

对于 30% 的数据，1 ≤ k ≤ n ≤ 1000
对于 100% 的数据， 1 ≤ k ≤ n ≤ 105, 1≤ ai ≤ 105

样例

输入样例1：

3 1
2 5 4
0 0 1

输出样例1：

输入样例2：

4 3
10 5 4 7
0 1 1 0

输出样例2：

19

分析及代码实现

• 先把可选的数求前缀和放在aa[ ] 中
• 再把所有的数求前缀和放在bb[ ] 中
• 通过变量ret 计算出在长度为k的区间上变化的最大值（两个前缀数组的差值的最大值）
• 最后将答案加上aa[ n ]即可。（aa[ n ]则表示所有可选的数的和）

c++代码实现

#include 
#include 
using namespace std;

typedef long long ll; //本题要用long long
const int N = 1e5 + 10;

ll aa[N], bb[N], a[N], b[N];
ll n, k, ret;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); //存数据
    for (int i = 1; i <= n; i++){
        scanf("%lld", &b[i]); //存状态
        aa[i] = aa[i - 1] + a[i] * b[i];//可选的数的前缀和
        bb[i] = bb[i - 1] + a[i];//所有数的前缀和
    }

    for (int i = k; i <= n; i++)
        //计算最大的差值，即增加的最大值
        ret = max(ret, (bb[i] - bb[i - k]) - (aa[i] - aa[i - k]));
    
    //最大的增大量+所有可选数的和 即为所求
    cout << ret + aa[n] << endl;
    return 0;
}