結果

問題 No.3114 0→1
コンテスト
ユーザー ponjuice
提出日時 2025-04-15 23:59:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 1,666 bytes
コンパイル時間 6,691 ms
コンパイル使用メモリ 277,776 KB
実行使用メモリ 14,360 KB
最終ジャッジ日時 2025-04-16 00:01:33
合計ジャッジ時間 8,276 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; i++)

int main(){
    // 入力
    int n;
    cin >> n;
    string s;
    cin >> s;

    // 00, 010 を含まない文字列が最適であるので、後ろ2文字を持つdpを行う

    // dp[i][0] := i文字目まで見たときに、後ろの文字が00であり、00,010を含まないのときの最小コスト(これは常にinf)
    // dp[i][1] := i文字目まで見たときに、後ろの文字が01であり、00,010を含まないのときの最小コスト
    // dp[i][2] := i文字目まで見たときに、後ろの文字が10であり、00,010を含まないのときの最小コスト
    // dp[i][3] := i文字目まで見たときに、後ろの文字が11であり、00,010を含まないのときの最小コスト

    int inf = 1e9;
    vector<vector<int>> dp(n+1, vector<int>(4, inf));
    dp[0][3] = 0; // 初期状態は何も見ていないので、00,010を含まないし11としてみても良い

    rep(i, 0, n) {
        if (s[i] == '0') {
            // 変更を加えない場合、110の場合のみ
            dp[i+1][2] = dp[i][3];
            // 変更を加え1にできる場合の遷移
            dp[i+1][1] = dp[i][2] + 1;
            dp[i+1][3] = min(dp[i][1] + 1, dp[i][3] + 1); // 実はdp[i][3] + 1からの遷移はいらないです(要証明)
        } else {
            dp[i+1][1] = dp[i][2];
            dp[i+1][3] = min(dp[i][1], dp[i][3]);
        }
    }

    // 最終的な答えは、dp[n]の最小値
    int ans = inf;
    rep(i, 0, 4) {
        ans = min(ans, dp[n][i]);
    }
    cout << ans << endl;
}
0