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ỉ ...
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
1 2 3 4 5 6 7 8 | <strong>Input:</strong> 1 5 5 5 1 6 10 20 1 8 6 10 20 <strong>Output:</strong> 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | 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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | 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]
