牛客—01分数规划

01分数规划

不清楚最优解时的"?"到底是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;

}