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 |
新手#include<stdio.h> #include<string.h> #include<algorithm> char a[200][40]; char b[200][40]; int dp[300][300]; int mark[300][300]; char c[300][40]; int cnt=0; void dfs(int x,int y) { if(x<=1||y<=1)return ; else dp[x][y]=0; // printf("%d %d\n",x,y); if(0==mark[x][y]) { strcpy(c[cnt++],a[x-1]); dfs(x-1,y-1); } else if(1==mark[x][y]) { dfs(x,y-1); } else if(-1==mark[x][y]) { dfs(x-1,y); } } int main() { char ch; int i,q,w,j; while(scanf("%s",&a[1][0])!=EOF) { cnt=0; for(i=2;;i++) { if(a[i-1][0]=='#')break; scanf("%s",&a[i][0]); } int n=i; for(i=1;;i++) { if(b[i-1][0]=='#')break; scanf("%s",&b[i][0]); } int m=i; for(i=0;i<=200;i++) { for(q=0;q<=200;q++) { dp[i][q]=0; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(strcmp(a[i],b[j])==0&&a[i][0]!='#'&&b[i][0]!='#') { dp[i+1][j+1]=dp[i][j]+1; mark[i+1][j+1]=0; } else { if(dp[i+1][j]>dp[i][j+1]) { dp[i+1][j+1]=dp[i+1][j]; mark[i+1][j+1]=1; } else { dp[i+1][j+1]=dp[i][j+1]; mark[i+1][j+1]=-1; } } } } // for(i=1;i<=n;i++) // { // for(q=1;q<=m;q++) // { // printf("%3d",dp[i][q]); // } // printf("\n"); // } // dfs(n,m);//printf("8888"); // for(i=1;i<=n;i++) // { // for(q=1;q<=m;q++) // { // printf("%3d",dp[i][q]); // } // printf("\n"); // } printf("%s",c[cnt-1]); for(i=cnt-2;i>=0;i--) { printf(" %s",c[i]); } printf("\n"); // printf("%d\n",dp[n][m]); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator