Xâu Chung Thưa Thớt
Points
48
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho hai dãy số nguyên $A$ gồm $N$ phần tử và $B$ gồm $M$ phần tử.
Biết rằng mỗi giá trị phân biệt xuất hiện không quá $5$ lần trong dãy $B$. Hãy tìm độ dài của dãy con chung dài nhất (Longest Common Subsequence) của $A$ và $B$.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên dương $N$ và $M$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$. Dòng thứ ba chứa $M$ số nguyên $B_1, B_2, \dots, B_M$.
Dữ liệu ra
In 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 5 1 2 3 4 5 3 4 1 2 5 |
3 |
| 6 7 1 2 1 3 2 4 2 1 3 1 4 2 3 |
4 |
Giới hạn
- $1 \le N, M \le 10^5$
- $1 \le A_i, B_i \le 10^9$
- Mỗi giá trị xuất hiện tối đa $5$ lần trong $B$
Community Discussion