不清楚最优解时的"?"到底是0还是1,就把这两种情况都遍历一遍!
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,i,cnt1,cnt0,cnt1_0,cnt0_0,fl1,fl0;
string s1;
cin>>t;
while(t--)
{
cin>>n;
cnt1=0;cnt0=0;cnt1_0=0;cnt0_0=0;fl1=0,fl0=0;
cin>>s1;
for(i=0;i<n;i++)
{
if(s1[i]=='1'||s1[i]=='?')
{
if(fl1==1)
{
cnt1++;
}
else
{
cnt1=1;
fl1=1;
}
if(cnt1>cnt1_0)
cnt1_0=cnt1;
}
else
{
if(cnt1>cnt1_0)
cnt1_0=cnt1;
fl1=0;
cnt1=0;
}
if(s1[i]=='0'||s1[i]=='?')
{
if(fl0==1)
{
cnt0++;
}
else
{
cnt0=1;
fl0=1;
}
if(cnt0>cnt0_0)
cnt0_0=cnt0;
}
else
{
if(cnt0>cnt0_0)
cnt0_0=cnt0;
fl0=0;
cnt0=0;
}
}
if(cnt0_0>cnt1_0) cout<<cnt0_0<<"\n";
else cout<<cnt1_0<<"\n";
}
return 0;
}