VOI 10 Bài 1 - Dãy con chung không liền kề dài nhất

View as PDF

Submit solution


Points: 0.08 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOI 2010
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Dãy C = ~c_{1}~ , ~c_{2}~ , ..., ~c_{k}~ là dãy con không liền kề của dãy A = ~a_{1}~ , ~a_{2}~ , ..., ~a_{m}~ nếu C có thể nhận được bằng cách chọn một dãy các phần tử không liền kề của A, nghĩa là tìm dược dãy các chỉ số ~i_{1}~ , ~i_{2}~ , ..., ~i_{k}~ sao cho:

1 ≤ ~i_{1}~ , ~i_{2}~ , ..., ~i_{k}~ ≤ m;

~i_{1} < i_{2} - 1, i_{2} < i_{3} - 1, \dots, i_{k - 1} < i_{k} - 1~;

~c_{1}~ = ~a_{i_1}~, ~c_{2}~ = ~a_{i_2}~, ..., ~c_{k}~ = ~a_{i_k}~.

Ta gọi độ dài của dãy số là số phần tử của nó.

Cho hai dãy:

A = ~a_{1}, a_{2}, \dots, a_{m}~

B = ~b_{1}, b_{2}, \dots, b_{n}~

Dãy C được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dãy con không liền kề của A, vừa là dãy con không liền kề của B.

Yêu cầu

Cho hai dãy số A và B. Hãy tìm độ dài của dãy con chung không liền kề dài nhất của hai dãy đã cho.

Input

  • Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ ~10^{3}~ ) được ghi cách nhau bởi dấu cách, lần lượt là số lượng phần tử của dãy A và dãy B.
  • Dòng thứ i trong m dòng tiếp theo chứa số nguyên không âm ~a_{i}~ (~a_{i}~ ≤ ~10^{4}~ ), i = 1, 2, ..., m.
  • Dòng thứ j trong n dòng tiếp theo chứa số nguyên không âm ~b_{j}~ (~b_{j}~ ≤ ~10^{4}~ ), j = 1, 2, ..., n.

Output

Ghi ra trên một dòng duy nhất độ dài của dãy con chung không liền kề dài nhất của hai dãy A và B.

Sample Input

4 5
4
9
2
4
1
9
7
3
4

Sample Output

2

Comments

Please read the guidelines before commenting.



  • -28
    iamqazolp  commented on Aug. 21, 2022, 1:36 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 22
    CODING  commented on Aug. 13, 2021, 12:33 p.m.

    Mn tham khảo ạ: https://www.youtube.com/watch?v=gODYcMfeLkY&t=322s