Cod sursa(job #1882520)

Utilizator cautionPopescu Teodor caution Data 17 februarie 2017 11:49:38
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1024;

int n, m;
int v1[kMaxN + 1], v2[kMaxN + 1], dp[kMaxN + 1][kMaxN + 1];
int lcs[kMaxN + 1];

int main()
{
	freopen("cmlsc.in", "rt", stdin);
	freopen("cmlsc.out", "wt", stdout);

	int i, j, x;

	scanf("%d %d", &m, &n);

	for (i = 1; i <= m; ++i) {
		scanf("%d", &x);
		v1[i] = x;
	}
	for (i = 1; i <= n; ++i) {
		scanf("%d", &x);
		v2[i] = x;
	}
	for (i = 1; i <= m; ++i) {
		for (j = 1; j <= n; ++j) {
			if (v1[i] == v2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	i = m; j = n;
	while (i > 0 && j > 0) {
		if (dp[i][j] == dp[i - 1][j - 1] + 1) {
			lcs[dp[i][j]] = v1[i];
			--i; --j;
		} else if (dp[i - 1][j] < dp[i][j - 1]) --j;
		else --i;
	}

	printf("%d\n", dp[m][n]);
	for (i = 1; i <= dp[m][n]; ++i) printf("%d ", lcs[i]);

	return 0;
}