本文最后更新于 963 天前,其中的信息可能已经有所发展或是发生改变。
3493. 最大的和 (滑动窗口)
描述
给定一个长度为 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:
输出样例1:
输入样例2:
输出样例2:
分析
- 该题目可将最大和分为两部分,即为可用状态的和
sum
以及选定区间内不可用状态的最大的和s
- 以选定区间的长度作为窗口,每次向右滑动,加上右边界状态为
0
的数,减去左边界状态为0
的数,维护一个最大值 - 循环遍历先求
sum
,再循环遍历窗口得到最大和,两者相加即为答案
代码