Cod sursa(job #703386)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 2 martie 2012 12:08:18
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define maxN 1030

int N , M , sol[maxN] , dp[maxN][maxN] , A[maxN] , B[maxN];

int main ()
{
	freopen ("cmlsc.in" , "r" , stdin);
	freopen ("cmlsc.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	for (int i = 1 ; i <= N ; ++i)
		scanf ("%d" , &A[i]);
	
	for (int i = 1 ; i <= M ; ++i)
		scanf ("%d" , &B[i]);
	
	
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 1 ; j <= M ; ++j)
			if (A[i] == B[j])
				dp[i][j] = max (dp[i - 1][j] , dp[i][j - 1]) + 1;
			
			else dp[i][j] = max (dp[i - 1][j] , dp[i][j - 1]);
	
	
	printf ("%d\n" , dp[N][M]);
	
	int dim = 0;
	
	for (int i = N , j = M ; i && j ;)
		if (A[i] == B[j])
		{
			sol[++dim] = A[i];
			
			--i , --j;
		}
		
		else if (dp[i - 1][j] > dp[i][j - 1])
			--i;
		
		else --j;
	
	
	for (int i = dim ; i >= 1 ; --i)
		printf ("%d " , sol[i]);
	
	return 0;
}