题解：P13894 [蓝桥杯 2023 省 C] 填充

题意比较明了，这里不在复述。

思路 1.0

我们考虑用贪心。

我们统计出所有两个相邻字符串相等的数量，然后在统计有多少个 ?，遇到时把它换成上一个字符答案加一即可，如果上一个字符是 ?，答案也加一。

CPP

for (int i = 2;i <= n;i++)
		if (s[i] == s[i - 1] || s[i] == '?' || s[i - 1] == '?') ans++,i++;

思路 2.0

我们考虑用动态规划。

设

dp_{i,0}

表示前

i

个字符以 0 结尾的最大子串数，

dp_{i,1}

表示前

i

个字符以 1 结尾的最大子串数。

首先，我们不必考虑前一个字符，就算前一个字符满足了我们动态规划所需要的字符，但我们也只会赋值给当前的状态，所以，我们要考虑前二个字符。

如果前二个字符是相等的，或者其中有的是 ? 时，当前状态就要和前二个状态的值加一取一个最大值。

CPP

cin >> s;
	n = s.size();
	for (int i = 2;i <= n;i++){
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
		if (s[i - 1] == '0' || s[i - 1] == '?')
			if (s[i - 2] == '0' || s[i - 2] == '?'){
				dp[i][0] = max(dp[i][0],dp[i - 2][0] + 1);
				dp[i][0] = max(dp[i][0],dp[i - 2][1] + 1);
			}
		if (s[i - 1] == '1' || s[i - 1] == '?')
			if (s[i - 2] == '1' || s[i - 2] == '?'){
				dp[i][1] = max(dp[i][1],dp[i - 2][0] + 1);
				dp[i][1] = max(dp[i][1],dp[i - 2][1] + 1);
			}
	}
	cout << max(dp[n][0],dp[n][1]) << endl;

题解：P13894 [蓝桥杯 2023 省 C] 填充

文章操作

思路 1.0

思路 2.0

相关推荐

评论

题解：P13894 [蓝桥杯 2023 省 C] 填充