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

Tác giả: flashmt

Ngôn ngữ: Pascal

var a,b:array[1..1000] of longint;
    i,j,m,n:longint;
    f:array[-1..1000,-1..1000] of integer;

begin
     read(m,n);
     for i:=1 to m do read(a[i]);
     for j:=1 to n do read(b[j]);
     for i:=-1 to 0 do
     begin
          for j:=0 to m do f[i,j]:=0;
          for j:=0 to n do f[j,i]:=0;
     end;
     for i:=1 to m do
         for j:=1 to n do
         begin
              if f[i-1,j]>f[i,j-1] then f[i,j]:=f[i-1,j]
              else f[i,j]:=f[i,j-1];
              if (a[i]=b[j]) and (f[i,j]<f[i-2,j-2]+1) then
                 f[i,j]:=f[i-2,j-2]+1;
         end;
     writeln(f[m,n]);
end.

Download