LCS2X spoj VOI2014 – Dãy con chung bội hai dài nhất

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

1. Đề bài LCS2X spoj

Dãy C = c1, c2, .. ck được gọi là dãy con của dãy A = a1, a2, .., an nếu C có thể nhận được bằng cách xóa bớt một số phần tử của dãy A và giữ nguyên thứ tự của các phần tử còn lại, nghĩa là tìm được dãy các chỉ số 1 ≤ l1 < l2 < … < lk ≤ n sao cho c1 = a_l1, c2 = a_l2, …, ck = a_lk. Ta gọi độ dài của dãy là số phần tử của dãy.

Cho hai dãy A = a1, a2, …, am và B = b1, b2, …, bn Dãy C = c1, c2, …, ck được gọi là dãy con chung bội hai của dãy A và B nếu C vừa là dãy con của dãy A, vừa là dãy con của dãy B và thỏa mãn điều kiện 2 × ci ≤ c(i+1) (i = 1, 2, …, k – 1).

Yêu cầu

Cho hai dãy A và B. Hãy tìm độ dài dãy con chung bội hai có độ dài lớn nhất của hai dãy A và B.

Input

Dòng đầu tiên chứa T là số lượng bộ dữ liệu. Tiếp đến là T nhóm dòng, mỗi nhóm cho thông tin về một bộ dữ liệu theo khuôn dạng sau:

  • Dòng đầu chứa 2 số nguyên dương m và n.
  • Dòng thứ hai chứa m số nguyên không âm a1, a2, …, am mỗi số không vượt quá 10^9.
  • Dòng thứ ba chứa n số nguyên không âm b1, b2, …, bn mỗi số không vượt quá 10^9.
  • Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Giới hạn

  • 30% số test có m, n <= 15.
  • 30% số test khác có m, n <= 150.
  • có 40% số test còn lại có m, n <= 1500.

Output

Ghi ra T dòng, mỗi dòng ghi một số nguyên là độ dài dãy con chung bội hai dài nhất của dãy A và B tương ứng với bộ dữ liệu vào.

Example

2. Hướng dẫn LCS2X spoj

Gọi F[i, j] là độ dài dãy con chung dài nhất của dãy A[1..i] và dãy B[1..j] thỏa điều kiện đề bài và A[i]=B[j].

Công thức truy hồi:

  • Nếu A[i]<>B[j] thì  F[i, j]=0
  • F[i, j]= Max{F[u, v]/ u<i, v<j}+1 và thỏa điều kiện đề bài. Có nghĩa là tồn tại 2 chỉ số k, t sao cho Max{F[u, v]/ u<i, v<j}=F[k,t] và A[k]*2<=A[i]; B[t]*2<=B[j]

Nhận xét:

  • Nếu cài đặt thông thường (sử dụng 4 vòng for i, j, u, v) độ phức tạp O(N4) chỉ giải quyết được 30% test.
  • Nếu ta thấy dãy con chung ( các phần tử được chọn ở dãy A và B giống nhau) ta có thể giải quyết với độ phức tạp O(N3) cụ thể:

Tính F[i, j]=  Max{F[i, v]/  v<j}+1 và thỏa điều kiện đề bài. Có nghĩa là tồn tại  chỉ số  t sao cho Max{F[i, v]/ v<j}=F[i,t] và B[t]*2<=A[i];

Với cách giải quyết này ta chỉ giải quyết được 60% test.

  • Để giải quyết hết các test ta có thể tính trước như sau:

+ Với mỗi i ta gọi Max_T là Max{F[i, j] đã được tính}và thỏa điều kiện đề bài.

+ Với mỗi i ta gọi D[j] là Max{F[i, j] đã được tính}

+ Khi đó F[i, j]= Max_T +1    Khi A[i]=B[j]

+ Max_T được cập nhật khi A[i]>=B[j]*2

+ D[j] được cập nhật khi A[i]=B[j]

 

3. Code tham khảo LCS2X spoj (pascal, C++)

 

[sociallocker]

a. Code LCS2X spoj Pascal

b. Code LCS2X spoj C++

 

[/sociallocker]

 

Trả lời

Thư điện tử 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 *