Cod sursa(job #180679)

Utilizator dan_10Dan Alexandru dan_10 Data 17 aprilie 2008 13:13:50
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream.h>


long int a[1050],b[1050],c[1050][1050],d[1050];
long int n,m,p;


int max(int x,int y)
{	if(x>y)return x ;
	return y;
}

void cmlsc()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		if(a[i]==b[j]) c[i][j]=c[i-1][j-1]+1;
		else c[i][j]=max(c[i-1][j],c[i][j-1]);

}
int main()
{
	ifstream f("cmlsc.in");
	ofstream g("cmlsc.out");

	f>>n>>m ;
	int i,j;
	for(i=1;i<=n;i++)
		f>>a[i];
	for(i=1;i<=m;i++)
		f>>b[i];
	cmlsc();
	int p=0;

	for(i=n;i>=1;i--)
	for(j=m;j>=1;j--)
		if(a[i]==b[j]) {	d[++p]=a[i];
					i--;
					j--;
			       }
		else  if(c[i-1][j]<=c[i][j-1]) j--;
		else  	i--;
	g<<p<<"\n";
	for(i=p;i>=1;i--)
	g<<d[i]<<" ";



	f.close();
	g.close();
	return 0;
}