AtCoder Beginner Contest 038 D - プレゼント - 宇宙ツイッタラーXの憂鬱

問題

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder

解法

最終的に重なった箱たちを内側から見た時、縦と横はそれぞれhとwの増加数列になっているはずである。このことから、もしhとwがそれぞれすべて異なる値で構成されている場合、ソートしてLISを取れば良さそうということが分かる。

これが成り立たないのはwが同じ値の箱をとってしまう場合である。これが成り立たないように予めhを降順にしておけば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int abc006_d(const vector<int> &cards) {
  int N = cards.size();
  vector<int> dp(N + 1, 1e9);
  dp[0] = -1e9;
  for (int i = 0; i < N; ++i) {
    int pos = lower_bound(dp.begin(), dp.end(), cards[i]) - dp.begin();
    dp[pos] = cards[i];
  }

  for (int i = N; i > 0; --i) {
    if (dp[i] < 1e9) return i;
  }
  assert(false);
  return -1;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<pair<int, int>> box(N);
  for (int i = 0; i < N; ++i) {
    int w, h;
    cin >> w >> h;
    box[i] = {w, -h};
  }
  sort(box.begin(), box.end());
  vector<int> cards(N);
  for (int i = 0; i < N; ++i) cards[i] = -box[i].second;

  cout << abc006_d(cards) << endl;
}