Búp Bê Hai Chiều

Buổi 39 — DP + Data Structures Dynamic Programming
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved