Cod sursa(job #1456679)

Utilizator valentin50517Vozian Valentin valentin50517 Data 1 iulie 2015 17:25:24
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
 
int rs[1030],r,A[1030],B[1030],D[1030][1030],M,N,i,j;
int main(){
	fin >> N >> M;
	for(i = 1;i<=N;i++){
		fin >> A[i];
	}
	for(i = 1;i<=M;i++){
		fin >> B[i];
	}
	
	for(i = 1;i<=N;i++)
		for(j = 1;j<=M;j++){
			if(A[i] == B[j]) D[i][j] = D[i-1][j-1] + 1;else
			D[i][j] = max(D[i-1][j],D[i][j-1]);
		}
	fout << D[N][M]<<'\n';
	
	for(i = N,j = M;i; ){
		if(A[i] == B[j]){
			rs[++r] = A[i];
			i--;
			j--;
		}else
		if(D[i-1][j] < D[i][j-1]) j--; else i--;
	}
	
	for(i = r;i>0;i--) fout << rs[i] <<' ';
	return 0;
}