LCS2X spoj VOI2014 – Dãy con chung bội hai 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

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

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 *