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.