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 |
N^3即可#include<iostream> using namespace std; #define maxn 500+5 int test,n,m; int f[maxn][maxn],s[maxn][maxn]; int a[maxn],b[maxn],ans[maxn]; int main() { int i,j,k,p,Max,I,J,now; test=1; while (test--) { scanf("%d",&n); for (i=1; i<=n; i++) scanf("%d",&a[i]); scanf("%d",&m); for (i=1; i<=m; i++) scanf("%d",&b[i]); /*f[i][j]表示a[1..i],与b[j]匹配最长长度*/ Max=I=J=0; for (i=1; i<=n; i++) for (j=1; j<=m; j++) { f[i][j]=f[i-1][j]; s[i][j]=-1; if (a[i]==b[j]) { p=0; for (k=1; k<j; k++) if (b[k]<b[j] && f[i-1][k]>f[i-1][p]) p=k; if (f[i-1][p]+1>f[i][j]) { f[i][j]=f[i-1][p]+1; s[i][j]=p; } } if (f[i][j]>Max) { Max=f[i][j]; I=i; J=j; } } printf("%d\n",Max); now=Max; while (now) { if (s[I][J]>-1) { ans[now--]=b[J]; J=s[I][J]; } I--; } for (i=1; i<Max; i++) printf("%d ",ans[i]); printf("%d\n",ans[Max]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator