题目描述
给定一个长度为 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:
9
输入样例2:
4 3
10 5 4 7
0 1 1 0
输出样例2:
19
import java.util.Scanner;
/**
* @author: yeah
* 意思就是可以使某一段 变为可选(原本是可选的还是可选),再加上其他原本就是可选的
* 这里的做法是两次前缀和
*/
public class Main {
static int n, k;
static long[] q = new long[100010], s = new long[100010];
static long[] tmp = new long[100010], ts = new long[100010];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
for (int i = 1; i <= n; i++) {
q[i] = in.nextLong();
s[i] = s[i - 1] + q[i];
}
for (int i = 1; i <= n; i++) {
int t = in.nextInt();
tmp[i] = t == 1 ? q[i] : 0;
ts[i] = ts[i - 1] + tmp[i];
}
long max = 0;
for (int i = n; i >= k; i--) {
//变为可选的加上原本就是可选的
max = Math.max((long) (s[i]) - s[i - k] + ts[i - k] + ts[n] - ts[i], max);
}
System.out.println(max);
}
}