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

weifengzhaomi · 2025-08-29 08:36:45 · 题解

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

思路 1.0

我们考虑用贪心。

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

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 结尾的最大子串数。

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

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

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;