Nikita and string [Codeforces Round #442 B]

http://codeforces.com/contest/877/problem/B

aとbからなる文字列Sがある。
この文字列から任意個数の文字列を抜いて、(任意個のa)(任意個のb)(任意個のa)の文字列を作る。
(任意個は0個でも良い)
作れる最大の文字数を求めよ。

len(S)≦5000

解法

http://codeforces.com/contest/877/submission/31636732

(任意個のb)の部分を全列挙して考える。
S[L,R]をbの部分と考えるとS[L,R]の'a'だけ抜くのが最適であり、前後のS[0,L-1]とS[R+1,N-1]は'b'だけ抜くのが最適である。
結局、抜いた後の文字列の長さは、(S[0,L-1]の'a'の個数)+(S[L,R]の'b'の個数)+([R+1,N-1]の'a'の個数)であるため、この最大値を求めれば答え。
　
個数計算を高速化しないと通らないが、累積和で計算できる。
「A[x] := S[0,x]の'a'の個数」としておくと、S[x,y]の'a'の個数は A[y]-A[x-1] で計算できる。
'b'も同様にやれば、区間の個数の取得はO(1)となって間に合う。
　
Hackポイントが(任意個のb)が0である場合も考慮する場合

string S;
int A[5010], B[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    int N = S.length();
    
    rep(i, 0, N) {
        if (S[i] == 'a') A[i] = 1;
        else B[i] = 1;
    }

    rep(i, 1, N) A[i] += A[i - 1];
    rep(i, 1, N) B[i] += B[i - 1];

    int ans = A[N-1];
    rep(L, 0, N) rep(R, L, N) {
        int a = 0;
        if (L) a = A[L - 1];
        int c = A[N - 1] - A[R];
        int b = B[R];
        if (L) b -= B[L - 1];

        ans = max(ans, a + b + c);
    }
    cout << ans << endl;
}