LNACS - Dãy con chung không liền kề
Dữ liệu vào: Standard input
Dữ liệu ra: Standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte


 

Dãy C = c1, c2, ..., ck là dãy con không liền kề của dãy A = a1, a2, ..., am 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ố i1, i2, ..., ik sao cho: 1 ≤ i1, i2, ..., ik ≤ m;  i1 < i2 - 1, i2 < i3 - 1, ..., ik - 1 < ik - 1;  c1 = ai1, c2 = ai2, ck = aik.

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

Cho hai dãy: A = a1, a2, ..., am  và  B = b1, b2, ..., bn. 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 2 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 2 dãy A,B.

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ 103) đượ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 ai (ai ≤ 104), i = 1, 2, ..., m.
  • Dòng thứ j trong n dòng tiếp theo chứa số nguyên không âm bj (bj ≤ 104), j = 1, 2, ..., n.

Kết quả:

Ghi ra 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.

 

Ví dụ

  • input
    1
    1
    0
    0
    output
    1
Back to Top