填充

1.题目

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

输入格式

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

输出格式

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

数据范围

对于所有评测用例，1≤n≤1061。

输入样例：

1110?0

输出样例：

2

样例解释

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

2.思路

简单来说，相邻的两个数字如果相同可以配对成功，1个数只能配对一次，如果是？，既可以和1配对，也可以和0配对。

根据观察可以看出，从左到右数，如果能配对则先配对，这样配对的数是最大的。这样从左循环到右边每个i都和i+1项目进行匹配，匹配成功后i++（for循环自带i++，所以相当于加两次，这样i+1就跳过和i+2的匹配了）result ++；这样的得出的result就是结果值。