Dãy con chung dài nhất của hai hoán vị
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho hai hoán vị $A$ và $B$ của các số nguyên từ $1$ đến $N$. Hãy tìm độ dài của dãy con chung dài nhất (LCS) của $A$ và $B$.
Lưu ý rằng $N$ có thể lên tới $10^5$ nên thuật toán $O(N^2)$ thông thường sẽ bị quá thời gian.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên mô tả hoán vị $A$.
- Dòng thứ ba chứa $N$ số nguyên mô tả hoán vị $B$.
Dữ liệu ra
- Một số nguyên duy nhất là độ dài dãy con chung dài nhất.
Ví dụ
| Input | Output |
|---|---|
| 5 3 2 1 4 5 1 2 3 4 5 |
3 |
Giới hạn
- $1 \le N \le 10^5$
Community Discussion