AtCoder Beginner Contest 038 D - プレゼント
解法
これ想定解かな…セグメント木を適当に使ったら解けました。
まず (h, w) のペアの順番にソートします。基本的にはこれで dp[i] = (i までの箱を使って最高いくつの入れ子を作れるか) というのを求めていきます。これで (hi, wi) を順番に見ていくことによって, h については考えなくても i < j を満たす (i, j) について hi < hj が保証されています。なので後は w についてだけです。
(hi, wi) について調べるときは, [0, wi) について dp の値が最高のものを取っていけば良いですが, これはセグメント木で実現できます。
一つ注意なのは, h の大きさが同じものについては, 逐一更新せずすべての dp を求めてから一気に更新しないといけないことに注意です。
// セグメント木(RMQ 対応) // update: k 番目の値を a に変更 // query: [l, r) の区間の最大値を求める template<typename T> struct ST { vector<T> seg; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(2*size-1, 0); } inline T merge(T x, T y) { return max(x, y); } void update(int k, T a) { k += size-1; seg[k] = a; while (k > 0) { k = (k-1)/2; seg[k] = merge(seg[k*2+1], seg[k*2+2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; const int MAXN = 100100; pair<int, int> P[MAXN]; int dp[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second; sort(P, P+N); ST<int> seg(MAXN); int ans = 0; for (int i = 0; i < N; ) { int ni = i+1; while (ni < N && P[i].first == P[ni].first) ni++; for (int j = i; j < ni; j++) { dp[j] = 1 + seg.query(0, P[j].second); ans = max(ans, dp[j]); } for (int j = i; j < ni; j++) { seg.update(P[j].second, max(dp[j], seg.query(P[j].second, P[j].second+1))); } i = ni; } cout << ans << endl; return 0; }