読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_1_D

Longest Increasing Subsequence | Aizu Online Judge


まずはTLEする回答
dp[i] := (i番目の数まで使った時の最長部分増加列の大きさ)
と定義しnについて2重ループを回せばO(n^2)で解ける.
すなわち a_i a_i以前の数 a_jより大きければ
 dp_i = max(dp_i,dp_j+1)
のような漸化式が書ける

int main()
{
  int n; cin >> n;
  vector<ll> a(n);
  vector<int> dp(n,1);
  REP(i,n) cin >> a[i];
  REP(i,n) REP(j,i) if(a[i] > a[j])
    dp[i] = max(dp[i],dp[j]+1);
  cout << *max_element(dp.begin(),dp.end()) << endl;
  return 0;
}

これでは不十分なのでもっと高速なアルゴリズムを考える.
dp[i] := (長さがi+1となるような部分増加列における最後の要素の最小値)
とおけばdpは単調増加列になる.なおそのような部分増加列が存在しない場合はINFを返す.
a[i]を0からn-1まで見て順次追加していく時, 追加するjは以下のようになる
 j=argmin(a_i \lt dp_j)
あとはそのような jを求めるアルゴリズムだがdpが単調増加列になっているのでこちらは二分探索でできる.
なおSTLにおいてlowerboundが同じ役目を持っており, こちらも二分探索のアルゴリズムによる.
結果O(nlog(n))の計算コストでできる.

#define LLINF 1LL << 60

int main()
{
  int n; cin >> n;
  vector<ll> a(n);
  vector<ll> dp(n,LLINF);
  REP(i,n) cin >> a[i];
  REP(i,n) *lower_bound(dp.begin(),dp.end(),a[i]) = a[i];
  cout << lower_bound(dp.begin(),dp.end(),LLINF)-dp.begin() << endl;
  return 0;
}