LNACS spoj – Dãy con chung không liền kề dài nhất

Nguồn đề bài: http://vn.spoj.com/problems/LNACS/

1. Đề bài LNACS spoj

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_m
và
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ụ

2. Gợi ý LNACS spoj

Bài này làm quy hoạch động tương tự bài dãy con chung dài nhất. Tuy nhiên có một chút khác ở công thức.

Gọi f[i][j] là độ dài dãy con chung dài nhất của 2 dãy a[1…i] và b[1…j]. Ta có:

• nếu a[i]!=b[j] thì: f[i][j]=max(f[i-1][j], f[i][j-1],f[i-1][j-1]).
• nếu a[i]==b[j] thì: f[i][j]=max(f[i-1][j], f[i][j-1],f[i-1][j-1],f[i-2][j-2]+1).

Về phần khởi tạo:

f[0][0] =0;

f[1][j]   = 1 nếu a[1]==b[j].

= f[1][j-1] nếu a[1]!=b[j].

f[i][1]   = 1 nếu a[i]==b[1].

= f[i-1][1] nếu a[i]!=b[1].

3. Code mẫu LNACS spoj