Dãy con chung tăng dài nhất

Buổi 24 — Mock Contest Phase 1
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.
Draft saved