Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:O(N*M) 算法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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator