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
Input: 1 5 5 5 1 6 10 20 1 8 6 10 20 Output: 3
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
uses math;
const fi='';
nmax=1500+100;
type
data=longint;
var
f:text;
n,m,test:data;
a,b,d:array[0..nmax] of data;
C:array[0..nmax,0..nmax] of data;
gtmax,res:data;
procedure QHD;
var i,j:data;
begin
res:=0;
for i:=0 to n do
d[i]:=0;
for i:=1 to m do
begin
gtmax:=0;
for j:=1 to n do
begin
if a[i]=b[j] then
c[i,j]:=gtmax+1;
if a[i]>=2*b[j] then
gtmax:=max(gtmax,d[j]);
if a[i]=b[j] then
begin
res:=max(res,c[i,j]);
d[j]:=max(d[j],c[i,j]);
end;
end;
end;
writeln(res);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,test);
for i:=1 to test do
begin
read(f,m,n);
for j:=1 to m do
read(f,a[j]);
for j:=1 to n do
read(f,b[j]);
QHD;
end;
close(f);
end;
begin
docfile;
end.b. Code LCS2X spoj C++
include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
//freopen("test.inp","r",stdin);
int t,m,n,i,j,a[1505],b[1505],c[1505],cur,prev;
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
scanf("%d%d",&m,&n);
for(i=0;i<m;++i) scanf("%d",&a[i]);
for(i=0;i<n;++i)
scanf("%d",&b[i]);
for(i=0;i<m;++i)
{
cur=0;
for(j=0;j<n;++j)
{
prev=cur;
if(2*b[j]<=a[i]) cur=max(cur,c[j]);
if(a[i]==b[j]) c[j]=max(c[j],prev+1);
}
}
cur=0;
for(i=0;i<n;++i) cur=max(cur,c[i]);
printf("%dn",cur);
}
}
[/sociallocker]
