牛客—01分数规划

于 2024-03-16 由 ciye 发布

[01分数规划][1]

[1]: https://ac.nowcoder.com/acm/contest/62977/D

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

分类：默认分类
标签：无标签

Ciyeblog

牛客—01分数规划

于 2024-03-16 由 ciye 发布

暂无评论

发表评论