Cod sursa(job #1431087)

Utilizator deleted_45f432468e7cd611DELETED deleted_45f432468e7cd611 Data 8 mai 2015 23:53:02
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>

void maxSubsequence (std::vector<int> &v, std::vector<int> &u, int m, int n) {

	int **c = (int**) malloc ((m+1) * sizeof(int*));

	for (int i = 0; i <= m; ++i) {
		c[i] = (int*) calloc (n + 1, sizeof(int));
	}

	for (int i = 0; i < m + 1; ++i) {
		c[i][0] = 0;
	}

	for (int j = 0; j < n + 1; ++j) {
		c[0][j] = 0;
	}

	std::vector<int> result;

	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (v[i-1] == u[j-1]) {

				c[i][j] = c[i-1][j-1] + 1;
				result.push_back (v[i-1]);
			} else {
				c[i][j] = std::max (c[i][j-1], c[i-1][j]);
			}
		}
	}

	std::ofstream g ("cmlsc.out");
	g << result.size() << "\n";

	for (unsigned int i = 0; i < result.size(); ++i) {
		g << result[i] << " ";
	}
	g << "\n";
	g.close();
}

int main (void) {
	std::ifstream f ("subsecvente.in");

	int m, n;
	f >> m >> n;

	std::vector <int> v (m);
	std::vector <int> u (n);

	for (int i = 0; i < m; ++i) {
		f >> v[i];
	}

	for (int i = 0; i < n; ++i) {
		f >> u[i];
	}

	maxSubsequence (v, u, m, n);

	v.clear();
	u.clear();
	f.close();
	return 0;
}