Xếp Lồng Phong Bì

Binary-search Dynamic Programming
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.
Draft saved