Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## O(N*M) 算法

Posted by byplane747 at 2011-08-03 16:32:20 on Problem 2127
```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
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.```

Followed by: