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

Re:O(N*M) 算法

Posted by wtw666 at 2016-07-04 22:34:29 on Problem 2127
In Reply To:O(N*M) 算法 Posted by:byplane747 at 2011-08-03 16:32:20
> 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.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator