本文主要是介绍第十四届蓝桥杯省赛大学C组（C/C++）填充，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：填充
有一个长度为 n 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 0 和 1 子串最多，输出子串个数。
输入格式
输入一行包含一个字符串。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于所有评测用例，1≤n≤10^6。
输入样例：
1110?0
输出样例：
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，防止重复利用。
代码实现：
#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;
}这篇关于第十四届蓝桥杯省赛大学C组（C/C++）填充的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
