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*m算法,递归输出路径,贴代码#include<cstdio> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std; #define N 505 int n,m,t; int s1[N],s2[N]; struct node { int p,key; }dp[N][N]; struct P { int pre,num; }p[N*N]; void f(int index) { if(index) { f(p[index].pre); printf("%d ",p[index].num); } } void DP() { memset(dp,0,sizeof(dp)); int ans=0,mx,i,j,fi,fj,tem,ansk; t=1; p[1].pre=0; for( i=1;i<=n;i++) { mx=0; fi=fj=0; for( j=1;j<=m;j++) { dp[i][j]=dp[i-1][j]; tem=dp[i][j].p; if(mx<tem&&s1[i-1]>s2[j-1]) { mx=tem; fi=i,fj=j; } if(s1[i-1]==s2[j-1]) { dp[i][j].p=mx+1; dp[i][j].key=t; p[t].num=s1[i-1]; p[t].pre=dp[fi][fj].key; t++; } if(ans<dp[i][j].p) { ans=dp[i][j].p; ansk=dp[i][j].key; } } } printf("%d\n",ans); f(ansk); printf("\n"); } int main() { scanf("%d",&n); int i; for( i=0;i<n;i++) scanf("%d",&s1[i]); scanf("%d",&m); for( i=0;i<m;i++) scanf("%d",&s2[i]); DP(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator