LNACS - VOI10 - Dãy con chung không liền kề dài nhất

Tác giả: skyvn97

Ngôn ngữ: Pascal

program LNACS;
const MAXN=1111;
var
        m,n:integer;
        a,b:array [-1..MAXN] of integer;
        f,g:array [-1..MAXN,-1..MAXN] of integer;
function max(x,y,z:integer):integer;
        begin
                if (x>=y) and (x>=z) then exit(x);
                if (y>=x) and (y>=z) then exit(y);
                if (z>=x) and (z>=y) then exit(z);
        end;
procedure init;
        var
                i:integer;
        begin
                read(m,n);
                for i:=1 to m do read(a[i]);
                for i:=1 to n do read(b[i]);
        end;
procedure optimize;
        var
                i,j,res:integer;
        begin
                res:=0;
                for i:=1 to m do
                        for j:=1 to n do
                                begin
                                        if a[i]=b[j] then f[i,j]:=g[i-2,j-2]+1;
                                        if f[i,j]>res then res:=f[i,j];
                                        g[i,j]:=max(g[i-1,j],g[i,j-1],f[i,j]);
                                end;
                write(res);
        end;
begin
        init;
        optimize;
end.

Download