关键是要证明对于每个长度为mid=(n+1)/2的区间，都有方法可以画满。

以n为偶数为例，如下图，意图在灰色区域画画，

首先在虚线处左右任意一侧画画，
如果当天是左边的坍塌了，就往左边画画，反之亦然
这就可以保证一定能将灰色区域画满
n为奇数也是一样的。

问题就变成寻找最大的，长度为mid的前缀和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 5e6+9;

char s[N];
int acc[N],q[N],cnt;

int main()
{
    int t,n;
    cin>>t;
    for(int ex=1;ex<=t;ex++){
        cin>>n;
        cin>>s+1;
        acc[1]=s[1]-'0';
        for(int i=2;i<=n;i++){
            acc[i]=acc[i-1]+s[i]-'0';
        }


        int ans= 0,len=(n+1)/2;
        for(int i=len;i<=n;i++){
            ans = max(ans,acc[i]-acc[i-len]);
        }


        printf("Case #%d: %d\n",ex,ans);

    }


    return 0;
}