Cod sursa(job #501224)

Utilizator costiniuliacostiniulia costiniulia Data 14 noiembrie 2010 16:51:32
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>

const int N=1050;

unsigned  char sol[N][N],x[N],y[N];
int a[N][N],n,m;

void drum(int i,int j)
{int r;
	if(a[i][j])
	{
		if(sol[i][j]==3)
			{r=x[i];	
				drum(i-1,j-1);
				printf("%d ",r);
			}
		else
			if(sol[i][j]==1)
				drum(i,j-1);
			else
				drum(i-1,j);
	}
}

int main()
{
 	freopen("cmlsc.in","r",stdin);
 	freopen("cmlsc.out","w",stdout);

		scanf("%d%d",&n,&m);

		int i,j,r;
			
			for(i=1;i<=n;++i)
				scanf("%d",&r),x[i]=r;

			for(i=1;i<=m;++i)
				scanf("%d",&r),y[i]=r;

			for(i=1;i<=n;++i)
				for(j=1;j<=m;++j)
					if(x[i]==y[j])
					{
						a[i][j]=a[i-1][j-1]+1;
						sol[i][j]=3;
					}
					else
						if(a[i][j-1]>a[i-1][j])
						{
							a[i][j]=a[i][j-1];
							sol[i][j]=1;
						}
						else
						{
							a[i][j]=a[i-1][j];
							sol[i][j]=2;
						}
	 
			printf("%d\n",a[n][m]);

			drum(n,m);


	return 0;
}