Cod sursa(job #1779914)

Utilizator rosuflaRosu Flaviu rosufla Data 15 octombrie 2016 18:08:14
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");

int vect[1030][1030],nr1,nr2;
int result[1030],contor=-1;
void form(){
	int aux;
	f>>nr1>>nr2;
	nr1 += 2;
	nr2 += 2;
	for(int i=2;i<nr1;++i){
		f>>aux;
		vect[0][i] = aux;
	}
	for(int i=2;i<nr2;++i){
		f>>aux;
		vect[i][0] = aux;
	}
}
int max(int a,int b){
	return (a>b) ? a : b;
}
void lms(){
	for(int i=2;i<nr2;++i){
		for(int j=2;j<nr1;++j){
			if((vect[i][0]==vect[0][j]) && (vect[i][j] + 1<=i))
				vect[i][j] += vect[i-1][j-1] + 1;
			else
				vect[i][j] = max(vect[i-1][j],vect[i][j-1]);
		}
	}
}
void rez(){
	int i = nr2-1;
	int j = nr1-1;
	while(i>=2&&j>=2){
		if(vect[i][0] == vect[0][j]){
			result[++contor] = vect[i][0];
			--i;
			--j;
		}
		else
		if(vect[i-1][j] >= vect[i][j-1])
			--i;
		else
			--j;
	}
}

void afis(){
	g << contor+1 << "\n";
	for(int i=contor;i>=0;--i)
		g << result[i] << " ";
	g << "\n";
}

int main(){
	form();
	lms();
	rez();
	afis();
	return (0);
}