Dãy con chung dài nhất của hai hoán vị

Buổi 71-72 — Ôn tập Dynamic Programming
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved