填充

问题描述

有一个长度为n的01串，其中有一些位置标记为?，这些位置上可以任意填充0或者1，请问如何填充这些位置使得这个01串中出现互不重叠的00和11子串最多，输出子串个数。

输入格式

输入一行包含一个字符串。

输出格式

输出一行包含一个整数表示答案

样例输入

1110?0

样例输出

2

样例说明

如果在问号处填0，则最多出现一个 00 和一个11:111000

解法

暴力：假设一共有m个问号，那么每个问号要么写0要么写1，则一共有2……m种写法

贪心：你找到了一个最优策略，利用这个策略可以直接找出最优解

假设字符串固定了，那么你该怎样让字符组成字串，使得合法字串最多？

对于中间的字符而言，优先和前面的匹配

str=input()
ans=0
li=[False for i in range(len(str))]#记录i位置是否匹配过
for i in range(len(str)):
    if str[i]!="?":
        if li[i]==False:
            if (i-1)>=0 and str[i-1]==str[i] and (li[i-1]==False):
                li[i-1]=True
                li[i]=True
                ans+=1
            elif (i+1)<len(str) and str[i+1]==str[i] and (li[i+1]==False):
                li[i]=True
                li[i+1]=True
                ans+=1
    else:
        if (li[i]):
            continue
        if (i-1)>=0 and (li[i-1]==False):
            li[i-1]=True
            li[i]=True
            ans+=1
        elif (i+1)<len(str) and (li[i+1]==False):
            li[i]=True
            li[i+1]=True
            ans+=1
print(ans)