AcWing 562. 壁画
原题链接
中等
作者:
冲凉冲
,
2024-03-01 10:13:17
,
所有人可见
,
阅读 62
//中间的墙被毁灭,则它左右一定无法摧毁,并且有一面墙没法画画,则会剩余一个墙面无法操作
//找(l,r)区间的数之和最大的
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e6+10;
int s[N];
int t;
int main(){
cin>>t;
for(int j=1;j<=t;j++){
int n;
cin>>n;
for(int i=1;i<=n;i++){
char p;
cin>>p;
s[i]=p-'0';
}
//前缀和
for(int i=1;i<=n;i++)s[i]+=s[i-1];
int ans=0;
for(int i=1;i+(n+1)/2-1<=n;i++){
ans=max(ans,s[i+(n+1>>1)-1]-s[i-1]);
}
cout<<"Case #"<<j<<": "<<ans<<endl;
}
return 0;
}