Cod sursa(job #791329)

Utilizator feelshiftFeelshift feelshift Data 23 septembrie 2012 19:55:20
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
// Sorin Davidoi ([email protected]) - 2012-09-23 19:08
// http://infoarena.ro/problema/cmlsc
#include <fstream>
using namespace std;

const int MAXSIZE = 1024 + 1;

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

int first[MAXSIZE], second[MAXSIZE];
int best[MAXSIZE][MAXSIZE];

void backtrack(int row, int column) {
	if(!row || !column) return;

	if(first[row] == second[column]) {
		backtrack(row-1,column-1);
		out << first[row] << ' ';
	}
	else
		if(best[row-1][column] > best[row][column-1])
			backtrack(row-1,column);
		else
			backtrack(row,column-1);
}

int main() {
	in >> first[0] >> second[0];

	for(int i = 1; i <= first[0]; ++i)
		in >> first[i];

	for(int i = 1; i <= second[0]; ++i)
		in >> second[i];

	for(int i = 1; i <= first[0]; ++i)
		for(int k = 1; k <= second[0]; ++k) {
			if(first[i] == second[k])
				best[i][k] = best[i-1][k-1] + 1;
			else
				best[i][k] = max(best[i-1][k],best[i][k-1]);
		}

	/*for(int i = 1; i <= first[0]; ++i) {
		for(int k = 1; k <= second[0]; ++k)
			out << best[i][k] << " ";
		out << endl;
	}*/

	out << best[first[0]][second[0]] << '\n';

	backtrack(first[0],second[0]);

	in.close();
	out.close();

	return (0);
}