POJ 3670 Eating Together

問題

1～3の数字からなる数列がある。この数列を単調非減少もしくは単調非増加にするために書き換える必要のある数字は最小でいくつか求めよ。なお数字は1～3にしか書き換えられない。

やりかた

DPでやった。
数列のうちの単調非減少なLISの長さをもとめると、それが書き換えなくて良い数字の数になる。なので数列の大きさからこの数を引くと書き換え無くてはならない数の個数になる。単調非増加についてももとめるため、数列をreverseしてもう一度同じことをやる。
TLEしないようO(NlogN)のやりかたでやる必要あり。

他の人のページを見るともっと良いやり方だった。。

using namespace std;

int dp[30010];
int main(int argc, char **argv){
  int N; scanf("%d", &N);
  vector<int> a(N);
  for(int i = 0; i < N; i++) 
    scanf("%d", &a[i]);

  int ans = INF;
  for(int k = 0; k <= 1; k++){
    FILL(dp, INF);
    for(int i = 0; i < N; i++) 
      *upper_bound(dp, dp + N, a[i]) = a[i];

    ans = min(ans, N - (int)(lower_bound(dp, dp + N, INF) - dp));
    reverse(ALL(a));
  }
  printf("%d\n", ans);
  return 0;
}