Dãy con chung tăng dài nhất
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho hai dãy số nguyên $A = (A_1, A_2, \dots, A_N)$ và $B = (B_1, B_2, \dots, B_M)$.
Hãy tìm độ dài lớn nhất của một dãy số $C$ sao cho $C$ vừa là dãy con (không nhất thiết liên tiếp) của $A$, vừa là dãy con của $B$, đồng thời $C$ là một dãy tăng ngặt ($C_1 < C_2 < \dots < C_k$).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N, M \le 2000$).
- Dòng thứ hai chứa $N$ số nguyên $A_1, \dots, A_N$ ($-10^9 \le A_i \le 10^9$).
- Dòng thứ ba chứa $M$ số nguyên $B_1, \dots, B_M$ ($-10^9 \le B_j \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là độ dài của dãy con chung tăng dài nhất.
Ví dụ
| Input | Output |
|---|---|
| 5 5 1 4 2 5 3 4 1 2 3 5 |
3 |
| 4 4 5 4 3 2 2 3 4 5 |
1 |
Giới hạn
- $1 \le N, M \le 2000$.
- $-10^9 \le A_i, B_j \le 10^9$.
Community Discussion