LCS2X – spoj

Đề bài:

Thuật toán:

  • Gọi L[i,j] là độ dài dãy con chung bội hai dài nhất với số cuối cùng là A[i] và B[j]1) Với A[i] <> B[j] thì L[i,j] = 0

    2) Với A[i] = B[j] thì L[i,j] = max(L[x,y] + 1) ( với x<i, y<j, A[x]*2 <= A[i] )

  • Để tính max(L[x,y]) nhanh chóng, ta sử dụng mảng F với ý nghĩa:F[y] = max(L[x,y])   =>Kết quả là max(F[j]) (với 1<=j<=n)

    Gọi ma=max(F[y]) ( với y<j, B[y]*2 <= A[i] )

    Khi đó ta có đoạn code phần xử lý sẽ là:

    for (i=1;i<=m;++i){
        ma=0;
        for (j=1;j<=n;++j){
            matruocj=ma;
            if (b[j]*2<=a[i]) ma=max(ma,f[j]);
            if (a[i]==b[j]) f[j]=max(f[j],matruocj+1);
        }
    }
  • Với cách này thì bạn chỉ cần dùng mảng 1 chiềuĐộ phức tạp: O(M*N)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        oo      =trunc(1e4);
 
var     a, b, f :array[0..oo] of longint;
        ma,matruocj     :longint;
        ans     :longint;
        m, n    :longint;
procedure Optimize;
var     i, j    :longint;
begin
        fillchar(f, sizeof(f),0);
        for i:=1 to m do
                begin
                        ma:=0;
                        for j:=1 to n do
                                begin
                                        matruocj:=ma;
                                        if b[j]*2<=a[i] then ma:=Max(ma,f[j]);
                                        if b[j]=a[i] then f[j]:=max(f[j],matruocj+1);
                                end;
                 end;
 
end;
 
Procedure run;
var     i, t,l :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(t);
        for l:=1 to t do
                begin
                        readln(m, n);
                        for i:=1 to m do read(a[i]);
                        for i:=1 to n do read(b[i]);
                        Optimize;
                        ans:=0;
                        for i:=1 to n do
                                if f[i]>ans then ans:=f[i];
                        writeln(ans);
                end;
        close(input);close(output);
end;
 
begin
        run;
end.

Đề thi, đáp án, kết quả PreVOI 2016