ABC038 D - プレゼント

やっぱり昔のABC-Dは難しい abc038.contest.atcoder.jp 自分用に解法メモなので日本語汚いです。

問題概要

・箱がN個ある
・i番目の箱の大きさは縦hi[cm],wi[cm]
・なるべく多くの箱を入れ子にする時最大で何重にすることができるか
・ある箱は縦、横がともに大きいサイズの箱にのみ入れることができる
※ある箱は1つまでしか他の箱を入れることができない ※箱は回転できない

N, h, w は10⁵以下

解法

dp[i] := i番目の箱が一番外側の時に入れ子にできる最大値
とする
dp[i] = max{dp[j] | hj < hi かつ wj < wi} + 1
である

--全ての箱の縦の長さhが全て異なる場合

縦の長さが小さい箱からdpを更新するようにする
dp[i] = max{dp[j] | j < i かつ wj < wi} + 1

つまりdp[i]を求める時にそれ以前に求めたdp[j]の中でwj<wiを満たすdp[j]の最大値が求まれば良い
wj < wiを満たす区間での最大値を求めれば良い
区間の最大値(最小値)を高速に求めるにはsegment treeを用いる

--同じhの箱がある場合

同じhで一番大きいwの箱のみ使えば良い

これで計算量がO(Nlog(max(w)))となって100点を取れる

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<int, int> P;
// セグメント木 [i,j)のmaxをlognで
const int NMAX = 1 << 18;
int N;
struct segment_tree_max {
    int n; vector<ll> v;
    segment_tree_max(int _n) {
        for (n = 1; n < _n; n *= 2);
        v = vector<ll>(n * 2 - 1, -1e9);
    }
    void set(int i, ll x) {
        int k = i + n - 1;
        v[k] = max(v[k], x);
        while (k > 0) {
            k = (k - 1) / 2;
            v[k] = max(v[k * 2 + 1], v[k * 2 + 2]);
        }
    }
    ll _get(int i, int j, int k, int l, int r) {
        if (r <= i || j <= l) return -1e9;
        if (i <= l && r <= j) return v[k];
        ll vl = _get(i, j, k * 2 + 1, l, (l + r) / 2);
        ll vr = _get(i, j, k * 2 + 2, (l + r) / 2, r);
        return max(vl, vr);
    }
    ll get(int i, int j) { return _get(i, j, 0, 0, n); }
};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  vector<P> vp(N);
  FOR(i,0,N) {
    cin >> vp[i].first >> vp[i].second;
    vp[i].second *= -1; // wでは降順に並び替えるため
  }
  sort(vp.begin(), vp.end());
  segment_tree_max st(100005);
  st.set(0, 0);
  FOR(i,0,N) {
    int h = vp[i].first, w = -vp[i].second;
    st.set(w, st.get(0, w) + 1);
  }
  cout << st.get(0, 100005) << endl;
  return 0;
}

segment tree強い