Búp Bê Hai Chiều
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ điểm trên mặt phẳng tọa độ, điểm thứ $i$ có tọa độ $(X_i, Y_i)$.
Bạn cần chọn ra một dãy gồm nhiều điểm nhất có thể sao cho có thể sắp xếp các điểm đã chọn thành một chuỗi $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$ thỏa mãn đồng thời $x_1 < x_2 < \dots < x_k$ và $y_1 < y_2 < \dots < y_k$.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương $N$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $X_i$ và $Y_i$.
Dữ liệu ra
In ra một số nguyên duy nhất là số lượng điểm tối đa có thể chọn.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 6 4 6 7 2 3 |
3 |
| 5 1 5 2 4 3 3 4 2 5 1 |
1 |
Giới hạn
- $1 \le N \le 2 \cdot 10^5$
- $-10^9 \le X_i, Y_i \le 10^9$
Community Discussion