Cod sursa(job #361531)

Utilizator sorecau_catalinSorecau Catalin sorecau_catalin Data 5 noiembrie 2009 18:46:03
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <algorithm>
using namespace std;

int a[256];
int b[256];
int c[256][256];
int m, n, i, j;
void Scrie(int i, int j);

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int main()
{
	
	fin >> n >> m;
	for ( i = 1; i <= n; ++i)
		fin >> a[i];
	for ( j = 1; j <= m; ++j) 
		fin >> b[j];
	
	for ( i = 1; i <= n; ++i )
		for ( j = 1; j <= m; ++j)
			if ( a[i] == b[j] )
				c[i][j] = 1 + c[i-1][j-1];
			else
				c[i][j] = max( c[i-1][j], c[i][j-1] );
	
	fout << c[n][m] << '\n';
	Scrie(n, m );
	fin.close();
	fout.close();
	return 0;
}

void Scrie( int i, int j)
{
	if ( i == 0 || j == 0 )
		return;
	if ( a[i] == b[j] )
	{
		Scrie( i-1, j-1 );
		fout << a[i] << ' ';
	}
	else
		if ( c[i-1][j] > c[i][j-1] )
			Scrie( i - 1, j );
		else
			Scrie( i, j - 1);
}