Xếp Lồng Phong Bì
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ chiếc phong bì hình chữ nhật, chiếc thứ $i$ có kích thước $(W_i, H_i)$ (không được xoay). Phong bì $A$ có thể lồng vào trong phong bì $B$ nếu $W_A < W_B$ và $H_A < H_B$. Hãy tìm số lượng phong bì nhiều nhất có thể 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$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $W_i, H_i$.
Dữ liệu ra
Một số nguyên duy nhất là số phong bì tối đa lồng được 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$.
Community Discussion