Dãy điểm tăng trên mặt phẳng
Points
65
AC Rate
0.0%
Time limit
1.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 độ nguyên $(x_i, y_i)$. Một dãy các điểm $P_1, P_2, \dots, P_k$ được gọi là tăng dần nếu với mọi $1 \le i < k$ đều thỏa mãn đồng thời $x_{P_i} < x_{P_{i+1}}$ và $y_{P_i} < y_{P_{i+1}}$. Hãy tìm độ dài lớn nhất của một dãy điểm tăng dần.
Cấu trúc con tối ưu: sắp xếp các điểm theo $x$ tăng dần, nếu $x$ bằng nhau thì theo $y$ giảm dần (để hai điểm cùng hoành độ không thể nối tiếp nhau), sau đó tìm LIS theo $y$ bằng $O(N \log N)$.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên $N$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$.
Dữ liệu ra
Một số nguyên duy nhất là độ dài dãy điểm tăng dài nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 6 4 6 7 2 3 |
3 |
| 3 1 1 1 1 1 1 |
1 |
Giới hạn
$1 \le N \le 10^5$, $|x_i|, |y_i| \le 10^9$.
Community Discussion