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; }