Cod sursa(job #1929792)

Utilizator Alex_AmarandeiAmarandei Matei Alexandru Alex_Amarandei Data 18 martie 2017 10:23:32
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#define max(a, b) (a > b) ? a : b 

using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int lcs[1030][1030], n, m, a[1030], b[1030], v[1030];

int main()
{
	int i, j, k = 1;

	fin >> n >> m;

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

	for (j = 1; j <= m; j++)
		fin >> b[j];

	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			if (a[i] == b[j])
				lcs[i][j] = 1 + lcs[i - 1][j - 1];
			else
				lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);

	fout << lcs[n][m] << '\n';

	while (i >= 1)
		if (lcs[i - 1][j - 1] == lcs[i][j] - 1)
		{
			v[k++] = a[i];
			i--; j--;
		}
		else
			if (lcs[i][j - 1] > lcs[i - 1][j])
				j--;
			else
				i--;

	for (i = k - 1; i >= 1; i--)
		fout << v[i] << ' ';

	fin.close();
	fout.close();
	return 0;
}