Xếp hộp lồng nhau

Buổi 71-72 — Ôn tập Dynamic Programming sorting
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ chiếc hộp chữ nhật 2D, chiếc hộp thứ $i$ có kích thước $(w_i, h_i)$ (không được xoay). Chiếc hộp $i$ có thể đặt lọt vào bên trong chiếc hộp $j$ nếu và chỉ nếu $w_i < w_j$ và $h_i < h_j$.

Hãy tìm số lượng hộp nhiều nhất có thể xếp lồng vào nhau thành một chuỗi.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i, h_i$ ($1 \le w_i, h_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là số hộp tối đa có thể xếp lồng vào nhau.
Ví dụ
Input Output
4
5 4
6 4
6 7
2 3
3
Giới hạn
  • $1 \le N \le 10^5, 1 \le w_i, h_i \le 10^9$
Draft saved