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