Cod sursa(job #688499)

Utilizator predator5047Butiu Alexandru Octavian predator5047 Data 23 februarie 2012 16:50:41
Problema Cel mai lung subsir comun Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <algorithm>
short d[1074][1028];

int main()
{
	short m,n,a[10260],b[1026],n2 = 0,v[1026];

	std::ifstream fin("cmlsc.in");
	
	fin >> m >> n;

	for(int i = 1; i <= m; ++i)
		fin >> a[i];
	
	for(int i = 1; i <= n; ++i)
		fin >> b[i];

	fin.close();

	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
		{
			if(a[i] == b[j])
				d[i][j] = d[i-1][j-1] + 1;
			else 
				d[i][j] = std::max(d[i-1][j],d[i][j-1]);
		}
	
	for(int i = m,j = n; i;)
	{
		if(a[i] == b[j])
		{
			v[++n2] = a[i];
			--j;
			--i;
		}
		else if(d[i-1][j] > d[i][j-1])
			--i;
		else
			--j;
	}

	std::ofstream fout("cmlsc.out");

	fout << n2 << '\n';

	for(int i = n2; i ; --i)
		fout << v[i] << " ";

	fout.close();
	return 0;
}