原题链接：填充
有一个长度为 n 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 0 和 1 子串最多，输出子串个数。
输入格式
输入一行包含一个字符串。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于所有评测用例，1≤n≤10^6。
输入样例：
代码语言：javascript复制1110?0输出样例：
代码语言：javascript复制2样例解释
如果在问号处填 0，则最多出现一个 00 和一个 11：111000。
解题思路：
主要利用动态规划思想，定义一个dp[i]表示遍历到第i个位置的最大字串个数。第i个位置可以由前一个位置转移，分下面三种情况：
1.如果当前位置为0，它前一位三种情况0，1，?，当前一位为0或？时可以凑成字串，dp[i]=dp[i-1] 1,否则无法凑成字串dp[i]=dp[i-1]。
2.如果当前位置为1，它前一位三种情况0，1，?，当前一位为1或？时可以凑成字串，dp[i]=dp[i-1] 1,否则无法凑成字串dp[i]=dp[i-1]。
3.如果当前位置为?，它前一位三种情况0，1，?，当前一位为0、1或？时可以凑成字串，dp[i]=dp[i-1] 1,否则无法凑成字串dp[i]=dp[i-1]。
我们每次把能够凑成字串的位置都标记为2，防止重复利用。
代码实现：
代码语言：javascript复制#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6 5;
string s;
int res;
int dp[N];
int main(){
cin>>s;
for(int i=1;i<s.size();i ){
if(s[i]=='0'){//第一种情况
if(s[i-1]=='0'||s[i-1]=='?'){
dp[i]=dp[i-1] 1;
s[i]=s[i-1]='2';
}
dp[i]=max(dp[i],dp[i-1]);
}
if(s[i]=='1'){//第二种情况
if(s[i-1]=='1'||s[i-1]=='?'){
dp[i]=dp[i-1] 1;
s[i]=s[i-1]='2';
}
dp[i]=max(dp[i],dp[i-1]);
}
if(s[i]=='?'){//第三种情况
if(s[i-1]=='0'||s[i-1]=='1'||s[i-1]=='?'){
dp[i]=dp[i-1] 1;
s[i]=s[i-1]='2';
}
dp[i]=max(dp[i],dp[i-1]);
}
}
cout<<dp[s.size()-1]<<endl;
return 0;
}
