定义数组 s 表示花的种类。其中,玫瑰和牡丹分别表示为 −1 和 1,则 ∣i=1∑nsi∣ 即为花坛的观赏度。
不难发现,对于区间 [l,r] 进行一次操作,区间贡献会变成其和的相反数,等价于 s 的总和减去两倍区间 [l,r] 的和。 所以我们分别计算 s 中子序列的最大值和最小值,以两值为边界枚举一遍,中间用 set 统计答案即可。
import java.util.HashSet;
import java.util.Scanner;
/**
* @Author: sj
* @Date: 2024-08-25
* @Description:
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] flowers = new int[n];
int sum = 0;
for(int i = 0; i < n; i++){
int a = scanner.nextInt();
if(a == 0){
a = -1;
}
flowers[i] = a;
sum += a;
}
int[] dp_max = new int[n + 1];
int[] dp_min = new int[n + 1];
dp_min[0] = 0;
dp_max[0] = 0;
for(int i = 0; i < n; i++){
dp_max[i + 1] = Math.max(dp_max[i] + flowers[i], flowers[i]);
dp_min[i + 1] = Math.min(dp_min[i] + flowers[i], flowers[i]);
}
int max = dp_max[1];
int min = dp_min[1];
for(int i = 2; i < n; i++){
if(dp_max[i] > max){
max = dp_max[i];
}
}
for(int i = 2; i < n; i++){
if(dp_min[i] < min){
min = dp_min[i];
}
}
HashSet set = new HashSet();
for(int i = min; i <= max; i++){
set.add(Math.abs(sum - 2 * i));
}
System.out.println(set.size());
}
}
from collections import defaultdict
n = int(input())
a = [int(x) if x != "0" else -1 for x in input().split()]
s = sum(a)
max_sum = 0
min_sum = 0
left = 0
right = 0
res = set()
for i in range(n):
max_sum = max(max_sum + a[i], a[i])
min_sum = min(min_sum + a[i], a[i])
left = min(left, min_sum)
right = max(right, max_sum)
for i in range(left, right+1):
res.add(abs(s - 2*i))
print(len(res))
小红喜欢玫瑰和牡丹,小红在他的花坛中种了 n 盆花,每盆花要么是玫瑰,要么是牡丹,并按顺序从左往右依次编号,从 1 到 n。花坛的观赏度定义为玫瑰与牡丹的盆数之差的绝对值。现在定义一种操作:选取一个连续的区间 [1,r],将编号从 1 到编号 r 的花盆中的玫瑰替换成牡丹,将牡丹替换成玫瑰。
小红不关心观赏度的高低,而是关心经过至多一次这样的操作,花坛可能出现的观赏度的种类数。请问经过至多一次这样的操作,小红的花坛一共有多少种不同的观赏度?
输入共两行:
输出一行,一个数字,表示经过至多一次操作后,花坛一共有多少种不同的观赏度。
2
0 1
2
4
0 1 1 0
3
【样例 #1】
不操作,观赏度为 0,
操作区间 [1,1],观赏度为 2,
操作区间 [2,2],观赏度为 2,
操作区间 [1,2],观赏度为 0,
共有 2 种不同的观赏度。