/* Thanh想在一面被均分为 N 段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分,这表示它的美观程度(如果它的上面有画的话)。
不幸的是,由于洪水泛滥,墙体开始崩溃,所以他需要加快他的作画进度!
每天 Thanh 可以绘制一段墙体。
在第一天,他可以自由的选择任意一段墙面进行绘制。
在接下来的每一天,他只能选择与绘制完成的墙面相邻的墙段进行作画,因为他不想分开壁画。
在每天结束时,一段未被涂颜料的墙将被摧毁(Thanh 使用的是防水涂料,因此涂漆的部分不能被破坏),且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。
Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。
Thanh想要保证,无论墙壁是如何被摧毁的,他都可以达到至少 B 的美观总分。
请问他能够保证达到的美观总分 B 的最大值是多少。
*/
/
@作者:梁嘉杰
data:2024/3/13
/
import java.io.*;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sa = new Scanner(System.in);
int T,N,B,i,j,x,a;
int[] arr = new int[5000001];
int[] arr1 = new int[5000001];
int[] arr2 = new int[5000001];
T = sa.nextInt();
for(i=0; i<T; i){
N = sa.nextInt();
arr[0] = 0;
a=0;
String next = sa.next();//数据预处理
char[] charArray = next.toCharArray();
for (int l = 0; l <N; l) {
arr[l+1] = charArray[l] - ‘0’;
}
for(j=1; j<=N; j){//前缀和
arr1[j] = arr[j] + arr1[j-1];
}
if(N%2 != 0) {
x = (N / 2) + 1;//奇数向上取整
for (j = x; j <= N; j) {
arr2[a] = arr1[j] - arr1[j-x];
// System.out.println(arr2[a]);
a;
}
}
else {
x = (N)/2;
for (j = x; j <= N; j) {
arr2[a] = arr1[j] - arr1[j-x];
a;
}
}
B = arr2[0];//返回最大值
for(j=1; j<a; j){
if(B < arr2[j]){
B = arr2[j];
}
}
System.out.println(“Case #” + (i+1) + “: ” + B);
}
}
}