DÃY CON CHUNG KHÔNG LIỀN KỀ DÀI NHẤT - mã: LNACS - SPOJ

Link: http://vn.spoj.com/problems/LNACS/

=======================================

Dãy C = c₁, c₂, ..., c_k là dãy con không liền kề của dãy A = a₁, a₂, ..., 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₁, i₂, ..., i_k sao cho:

1 ≤ i₁, i₂, ..., i_k ≤ m;

i₁ < i₂ - 1, i₂ < i₃ - 1, ..., i_{k - 1} < i_k - 1;

c₁ = a_i1, c₂ = a_i2, c_k = a_ik.

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

Cho hai dãy:

A = a₁, a₂, ..., a_mvà

B = b₁, b₂, ..., 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.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ 10³) đượ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⁴), 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⁴), j = 1, 2, ..., n.

Kết quả

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.

Ví dụ

Input:

4 5

4

9

2

4

1

9

7

3

4

Output:

2

===============

Sử dụng Quy hoạch động

Công thức truy hồi:

F[i,j]:=F[i-2,j-2]+1 nếu A[i]=B[j]

F[i,j]:=max(F[i-1,j],F[i,j-1])

Tạo cơ sở quy hoạch động:

F[i,1]:=1 nếu A[i]=B[1] ngược lại F[i,1]:=F[i-1,1];

F[1,j]:=1 nếu A[1]=B[j] ngược lại F[1,j]:=F[1,j-1];

==============

Code: LNACS