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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

1. Đề bài LNACS spoj

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

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 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 ≤ 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 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

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *