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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    if (n < 2) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<int>> dp(n, vector<int>(2, 0));
    if (s[0] == '0') {
        dp[0][0] = 0;
        dp[0][1] = -1;
    } else if (s[0] == '1') {
        dp[0][0] = -1; 
        dp[0][1] = 0;
    } else { // '?'
        dp[0][0] = 0;
        dp[0][1] = 0;
    }
    
    for (int i = 1; i < n; i++) {
        if (s[i] == '0' || s[i] == '?') {
            // 不形成子串
            int max_val = max(dp[i-1][0], dp[i-1][1]);
            if (dp[i-1][0] != -1) {
                max_val = max(max_val, dp[i-1][0] + 1);
            }
            dp[i][0] = max_val;
        } else {
            dp[i][0] = -1;
        }
        if (s[i] == '1' || s[i] == '?') {
            int max_val = max(dp[i-1][0], dp[i-1][1]);
            if (dp[i-1][1] != -1) {
                max_val = max(max_val, dp[i-1][1] + 1);
            }
            dp[i][1] = max_val;
        } else {
            dp[i][1] = -1;
        }
    }
    
    int result = max(dp[n-1][0], dp[n-1][1]);
    cout << result << endl;
    
    return 0;
}