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

Tamflexの貯蔵庫

やる気のない備忘録

abc 038


LISの二次元バージョン.x座標でソートしてy座標のLISを求めればいい

ここでうまいと思ったのはy座標を負にすること.
問題では狭義単調増加の最長増加列を求めさせているので,x座標が同じだと条件に合わない.
そこで負にすることで絶対値が大きい順に並べこれを避けている.
自分はここの処理に戸惑ってうまくいかなかったので次回以降参考にしたい.
もうひとつ一般にn次元でどうとけばいいのか考えてみたい.

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