Cod sursa(job #812365)

Utilizator trifan_gabrielaTrifan Gabriela trifan_gabriela Data 13 noiembrie 2012 20:01:09
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>

using namespace std;

int n, m;
int a[1025], b[1025];
int Lcs[1025][1025], X[1025][1025];

void citire();
void pd();
void afisare();

int main()
{
	citire();
	pd();
	afisare();
	return 0;
}

void citire()
{
	ifstream fin ("cmlsc.in");
	int i;
	fin>>n>>m;
	for(i=0;i<n;i++)
		fin>>a[i];
	for(i=0;i<m;i++)
		fin>>b[i];
}

void pd()
{
	int i, j;
	for(i=n-1;i>=0;i--)
		for(j=m-1;j>=0;j--)
			if(a[i]==b[j])
			{
				Lcs[i][j]=1+Lcs[i+1][j+1];
				X[i][j]=1;
			}
			else
				if(Lcs[i+1][j]>Lcs[i][j+1])
				{
					Lcs[i][j]=Lcs[i+1][j];
					X[i][j]=2;
				}
				else
				{
					Lcs[i][j]=Lcs[i][j+1];
					X[i][j]=3;
				}
}

void afisare()
{
	ofstream fout ("cmlsc.out");
	int i, j;
	i=j=0;
	fout<<Lcs[0][0]<<'\n';
	while(i<n && j<m)
		if(X[i][j]==1)
		{
			fout<<a[i]<<' ';
			i++;
			j++;
		}
		else
			if(X[i][j]==2)
				i++;
			else
				if(X[i][j]==3)
					j++;
}