题目描述
给定一个长度为 $n$ 的正整数数列 $a_1,a_2,…,a_n$。
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 $k$ 的区间 $[i,i+k−1]$,使得 $a_i∼a_{i+k−1}$ 这 $k$ 个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
输入格式
第一行包含两个整数 $n$ 和 $k$。
第二行包含 $n$ 个整数 $a_i$。
第三行包含一个长度为 $n$ 的 $01$ 序列,如果第 $i$ 个数为 $1$,表示 $a_i$ 的初始状态为可选,如果第 $i$ 个数为 $0$,表示 $a_i$ 的初始状态为不可选。
输出格式
一行一个整数,表示答案。
数据范围
对于 $30\%$ 的数据,$1≤k≤n≤1000$
对于 $100\%$ 的数据,$1≤k≤n≤10^5,1≤a_i≤10^5$
输入样例1
3 1
2 5 4
0 0 1
输出样例1
9
输入样例2
4 3
10 5 4 7
0 1 1 0
输出样例2
19
算法1
(前缀和 + 滑动窗口)
- 维护两个前缀和数组
s1
和s2
,其中s1
表示没有选择限制的前缀和,s2
表示在可选状态下的前缀和 - 维护一个长度为
k
的定长窗口,每次计算这个窗口内所有元素如果全部变成可选状态会带来的增量,然后取所有增量的最大值 - 答案原本可选区间的和加上长度为
k
的窗口所能带来的最大增量
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
long[] s1 = new long[n+1];
long[] s2 = new long[n+1];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
for(int i = 0; i < n; i++) b[i] = sc.nextInt();
for(int i = 1; i <= n; i++) {
s1[i] = s1[i-1] + a[i-1];
if(b[i-1] == 1) s2[i] = s2[i-1] + a[i-1];
else s2[i] = s2[i-1];
}
long diff = 0;
for(int i = k; i <= n; i++){
diff = Math.max(diff, (s1[i] - s1[i-k]) - (s2[i] - s2[i-k]));
}
System.out.println(s2[n] + diff);
}
}
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
算法2
(滑动窗口)
- 方法1可以进一步优化空间:由于窗口定长,所以可以直接利用一个变量来记录每个窗口所带来的增量,最后取最大值。具体地,如果一开始为不可选状态,则记录不可选状态的和,如果窗口长度超过
k
,则把末尾的元素移除,如果末尾元素为可选状态,则直接忽略。
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for(int i = 0; i < n; i++) a[i] = sc.nextInt();
for(int i = 0; i < n; i++) b[i] = sc.nextInt();
// 可选数的和
long sum1 = 0;
for(int i = 0; i < n; i++){
if(b[i] == 1) sum1 += a[i];
}
// 不可选数的和
long sum2 = 0;
long maxv = 0;
for(int i = 0; i < n; i++){
if(b[i] == 0) sum2 += a[i];
if(i - k >= 0 && b[i - k] == 0) sum2 -= a[i - k];
maxv = Math.max(maxv, sum2);
}
System.out.println(sum1 + maxv);
}
}
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$,不算输入所占用的空间