D - 101 to 010

https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_d

解法

11110111のように0の左右に1が並んでいるとき、左か右の個数回だけ操作でき、逆側の1の個数を1減らす

上のように左右に1を持つ0について、左か右の1をいくつか取る問題になる

ランレングス圧縮して、0が2つ以上並んでいるところで分割してそれぞれの部分問題を解くとやりやすい

また、左右の1を取る個数は0 か 全てか 1つ残すのどれか 

dpでせんいする

https://atcoder.jp/contests/code-festival-2017-qualb/submissions/4794451

vp run_length(vi a) {
    vp ret;
    ret.eb(a[0], 1);
    rep(i, 1, sz(a)) {
        if (ret.back().fi == a[i]) {
            ret.back().se++;
        } else {
            ret.eb(a[i], 1);
        }
    }
    return ret;
}
vector<pair<char, int>> run_length(string &a) {
    vector<pair<char, int>> ret;
    ret.eb(a[0], 1);
    rep(i, 1, sz(a)) {
        if (ret.back().fi == a[i]) {
            ret.back().se++;
        } else {
            ret.eb(a[i], 1);
        }
    }
    return ret;
}
void solve() {
    cin>>n>>s;
    s = "101000" + s + "000010100000";
    auto run = run_length(stov(s));
    vvi(a);
    fora(v, run) {
        //trim
        if (v.fi == 0 && v.se > 1) {
            a.pb(b);
            b.clear();
        } else {
            b.pb(v.fi * v.se);
        }
    }
    auto calc = [&](vi &a) {
        if (a.front())pf(a, 0);
        if (a.back() == 0)a.pop_back();
        int n = sz(a);
        vvi(dp, n + 1, 4);
        //0index [i]がmu hid mig mig(一つ残す) の最高値
        dp[0][0] = 0;
        rep(i, 2, n - 1) {
            if (a[i])continue;
            //* 0
            chma(dp[i][0], max(dp[i - 2]));

            //0 l
            chma(dp[i][1], dp[i - 2][0] + a[i - 1]);
            //l l
            chma(dp[i][1], dp[i - 2][1] + a[i - 1] - 1);
            //r l
            chma(dp[i][1], dp[i - 2][2]);
            //r1 l
            chma(dp[i][1], dp[i - 2][3] + 1);

            //0 r
            chma(dp[i][2], dp[i - 2][0] + a[i + 1]);
            //l r
            if (a[i - 1] > 1)chma(dp[i][2], dp[i - 2][1] + a[i + 1]);
            //r r
            chma(dp[i][2], dp[i - 2][2]);
            //r1 r
            chma(dp[i][2], dp[i - 2][3] + a[i + 1]);

            //0 r1
            chma(dp[i][3], dp[i - 2][0] + a[i + 1] - 1);
            //l r1
            if (a[i - 1] > 1)chma(dp[i][3], dp[i - 2][1] + a[i + 1] - 1);
            //r r1
            chma(dp[i][3], dp[i - 2][2]);
            //r1 r1
            chma(dp[i][3], dp[i - 2][3] + a[i + 1] - 1);
        }
        return max(dp);
    };
    int cou = 0;
    fora(v, a) {
        cou += calc(v);
    }
    cout << cou - 2 << endl;
}

void solve() {
    str s;
    cin >> n >> s;
    s += '0';
    vi nez(n + 3);
    vi dp(n + 3);
    rer(i, n - 1) {
        if (s[i + 1] == '0')nez[i] = i + 1;
        else nez[i] = nez[i + 1];
    }
    //dp[i)
    rep(i, n) {
        chma(dp[i + 1], dp[i]);
        //左端とする
        if (s[i] == '1') {
            //左を全部取る
            if (nez[i] + 1 < n && s[nez[i] + 1] == '1') {
                chma(dp[nez[i] + 2], dp[i] + nez[i] - i);
            }
            //自分から右へ取る
            if (i + 2 < n && s.substr(i, 3) == "101") {
                int rb = nez[i + 1];
                chma(dp[rb], dp[i] + (rb - (i + 2)));
                chma(dp[rb - 1], dp[i] + (rb - (i + 2) - 1));
            }
        }
    }
    cout << dp[n] << endl;
}