var
  f,pa,pb:array[0..500,0..500]of longint;
  a,b,c:array[1..500]of longint;
  n,m,i,j,k,ans,num:longint;
procedure init;
begin
  readln(n); for i:=1 to n do read(a[i]);
  readln(m); for i:=1 to m do read(b[i]);
end;
procedure doit;
var
  max,pre,x,y:longint;
begin
  fillchar(f,sizeof(f),0);
  fillchar(pa,sizeof(pa),0);fillchar(pb,sizeof(pb),0);
  for i:=1 to n do
  begin
    max:=0;pre:=0;
    for j:=1 to m do
    begin
      if a[i]<>b[j] then
      begin
        f[i,j]:=f[i-1,j]; pa[i,j]:=pa[i-1,j];
      end else
      begin
        f[i,j]:=max+1; pa[i,j]:=i;pb[i,j]:=pre;
      end;
      if (a[i]>b[j])and(max<f[i-1,j]) then
      begin
        max:=f[i-1,j]; pre:=j;
      end;
    end;
  end;
  ans:=0;
  for i:=1 to m do if f[n,i]>ans then
  begin
    ans:=f[n,i]; y:=i;
  end;
  writeln(ans);
  if ans>0 then
  begin
    num:=ans; x:=pa[n,y];
    while y>0 do
    begin
      c[num]:=b[y];dec(num); y:=pb[x,y];x:=pa[x-1,y];
    end;
    for i:=1 to ans-1 do write(c[i],' '); writeln(c[ans]);
  end else writeln;
end;
begin
  init;doit;
end.

• Re:O(N*M) 算法 (1215) wtw666 2016-07-04 22:34:29