Cod sursa(job #1126117)

Utilizator superman_01Avramescu Cristian superman_01 Data 26 februarie 2014 21:21:46
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 1026
#define get_max(a,b) ((a)>(b)?(a):(b))

using namespace std;

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

int DP[NMAX][NMAX] , N , M , A[NMAX] , B[NMAX] ;
vector < int > Sol;

int main ( void )
{
	int i , j ;
	in >> N >> M ;
	for ( i = 1 ; i <= N ; in >> A[i++] );
	for ( i = 1 ; i <= M ; in >> B[i++] );
	for ( i = 1 ; i <= N ; ++i )
		for ( j = 1 ; j <= M ; ++j )
			if ( A[i] == B[j] )
				DP[i][j] = DP[i-1][j-1] + 1 ;
			else DP[i][j] = get_max ( DP[i][j-1] , DP[i-1][j] );
	out << DP[N][M] << "\n";
	for ( i = N , j = M ; i ; )
		if ( A[i] == B[j] ) Sol.push_back(A[i]) , --i  , --j;
	else
		if ( DP[i][j-1] > DP[i-1][j] ) --j;
	else --i;
	reverse ( Sol.begin() , Sol.end());
	for ( vector < int > ::iterator it = Sol.begin () ; it != Sol.end() ; ++it ) out << *it << " ";		
	in.close();
	out.close();
	return 0;
}