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

alst_1 · 2025-08-29 08:05:30 · 题解

一道贪心的题，但是我的方法是动态规划，动态规划可以更系统地处理每个位置的状态，并选择最优的填充方式。 代码:

#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;
}

结束！