C - 01文字列

https://atcoder.jp/contests/ddcc2016-final/tasks/ddcc_2016_final_c

解法

ランレングス圧縮する

最初に追加した区間がtのどの位置か決めると組み立て方が一意に定まる

累積和

https://atcoder.jp/contests/ddcc2016-final/submissions/5008563

void solve() {
    din(a, b, c);
    str t = sin();
    minu(t, '0');
    au ra = run_length(t);
    n = sz(ra);
    au rui = ruic(values(ra));
    rep(i, n) {
        int cou = 0;
        cou += rui[i] * a;
        cou += rui(i + 1, n) * b;//自分ふくまず
        int ad = MAX(ll);
        //0
        if (ra[i].fi == 0) {
            //0
            //01
            int l = i;
            int r = n - i - 2;
            int len = max(l, r);
            if (od(len))len++;
            chmi(ad, len * c + a * ra[i].se);
            // 0
            //01   1をおく
            l = i - 1;
            r = n - i - 1;
            len = max(l, r);
            if (ev(len))len++;
            chmi(ad, len * c + b * ra[i].se);
        } else {
            //1
            //01
            int l = i;
            int r = n - i - 2;
            int len = max(l, r);
            if (ev(len))len++;
            int v = len * c;
            chmi(ad, len * c + a * ra[i].se);
            // 1
            //01
            l = i - 1;
            r = n - i - 1;
            len = max(l, r);
            if (od(len))len++;
            chmi(ad, len * c + b * ra[i].se);
        }
        chmi(cou + ad);
//        cout << mi << endl;
    }
    cout << mi << endl;
}