| ||||||||||
| 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