Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

新手

Posted by 13926491 at 2016-03-02 20:32:50 on Problem 2250
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator