Codeforces Round #334 (Div. 1) A. Alternative Thinking

出るつもりだったのに開始時間を勘違いして出れなかったこどふぉ。

問題

codeforces.com

解法

もっと簡単に解けるらしいですが, dp で解きました。

dp[now][start][use] = (now 番目の数字を見ていて, 最初の数字は start にするつもり, 反転させているフラグは use で与えられるときの, 求める最長文字列) を考えます。

use は, 0 の時はもう反転させる部分文字列は決まっていて, 1 の時は反転させる部分文字列を伸ばしている途中, 0 の時はまだ反転させる部分文字列を選んでいない, という状態です。

dp の遷移は面倒ですが明らかなのでコードを見て下さい…(思ったより面倒だった…)

const int MAXN = 100100;
int n;
string s;

// 0:使い終わった 1:使ってる 2:まだ
int dp[MAXN][2][3];

int dfs(int now, int start, int use) {
    if (now == n) {
        if (use == 2) return -MAXN;
        else return 0;
    }
    int& ret = dp[now][start][use];
    if (ret > -MAXN) return ret;
    if (s[now] == '0' && start == 0) {
        if (use == 0) ret = max(ret, 1+dfs(now+1, 1, use));
        if (use == 1) {
            int tmp = 1+dfs(now+1, 1, 0); // やめる
            tmp = max(tmp, dfs(now+1, 0, use)); // やめない
            ret = max(ret, tmp);
        }
        if (use == 2) {
            int tmp = 1+dfs(now+1, 1, 2);
            ret = max(ret, tmp);
        }
    } else if (s[now] == '0' && start == 1) {
        if (use == 0) ret = max(ret, dfs(now+1, 1, use));
        if (use == 1) {
            ret = max(ret, 1+dfs(now+1, 0, 1));
        }
        if (use == 2) {
            int tmp = 1+dfs(now+1, 0, 1);
            tmp = max(tmp, dfs(now+1, 1, 2));
            ret = max(ret, tmp);
        }
    } else if (s[now] == '1' && start == 0) {
        if (use == 0) ret = max(ret, dfs(now+1, 0, use));
        if (use == 1) {
            ret = max(ret, 1+dfs(now+1, 1, 1));
        }
        if (use == 2) {
            int tmp = dfs(now+1, 0, 2);
            tmp = max(tmp, 1+dfs(now+1, 1, 1));
            ret = max(ret, tmp);
        }
    } else {
        if (use == 0) ret = max(ret, 1+dfs(now+1, 0, use));
        if (use == 1) {
            ret = max(ret, dfs(now+1, 1, use));
            ret = max(ret, 1+dfs(now+1, 0, 0));
        }
        if (use == 2) {
            ret = max(ret, 1+dfs(now+1, 0, use));
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    cin >> s;
    for (int i = 0; i <= n; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 3; k++) {
        dp[i][j][k] = -MAXN;
    }
    cout << max(dfs(0, 0, 2), dfs(0, 1, 2)) << endl;
    return 0;
}