はまやんはまやんはまやん

hamayanhamayan's blog

A Twisty Movement [Codeforces Round #462 (Div. 1) A]

http://codeforces.com/contest/933/problem/A

N要素の配列Aがある。
ここから任意の連続する列を選択し、左右反転する操作を1度だけ行える。
作れる広義単調増加列の長さの最大値は?

解法

http://codeforces.com/contest/933/submission/35279466

数は1か2しかないため、広義単調増加列は前半が1,後半が2となる列となる。
スワップできることを考えると、今回の問題は以下のように言い換えられる。
「配列Aを4つに分けた時に、1番目の1の数+2番目の2の数+3番目の1の数+4番目の2の数を最大化せよ」
 
これを実現するために2つのDPを事前計算しよう。
dp[i] := A[0,i]で前半1後半2となる列の1+2の数の最大値
dp2[i] := A[i,N-1]で前半1後半2となる列の1+2の数の最大値
これが計算できれば、答えはdp[i]+dp2[i+1]の最大値となる。
このDPは簡単な2重ループで解ける。
区間の1の数や2の数は累積和をとっておくと高速に取得できる。

int N, A[2020], sm[2020], dp[2020], dp2[2020];
//---------------------------------------------------------------------------------------------------
void pre() {
    rep(i, 0, N) if (A[i] == 1) sm[i] = 1;
    rep(i, 1, N) sm[i] += sm[i - 1];
}
int getone(int l, int r) { // [l,r]
    int res = sm[r];
    if (l) res -= sm[l - 1];
    return res;
}
int gettwo(int l, int r) { // [l,r]
    return (r - l + 1) - getone(l, r);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    pre();

    rep(i, 0, N) {
        dp[i] = max(getone(0, i), gettwo(0, i));
        rep(j, 0, i) chmax(dp[i], getone(0, j) + gettwo(j + 1, i));
    }

    rep(i, 0, N) {
        dp2[i] = max(getone(i, N - 1), gettwo(i, N - 1));
        rep(j, i + 1, N) chmax(dp2[i], getone(i, j - 1) + gettwo(j, N - 1));
    }

    int ans = 1;
    rep(i, 1, N) chmax(ans, dp[i - 1] + dp2[i]);
    cout << ans << endl;
}