Cod sursa(job #3200416)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 4 februarie 2024 16:50:24
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <stdio.h>

int32_t max(int32_t val1, int32_t val2) {
	return (val1 > val2) ? val1 : val2;
}

const int32_t MAX_M = 1024;
const int32_t MAX_N = 1024;

int32_t vec1[MAX_M], vec2[MAX_N];
int32_t dp[MAX_M][MAX_N];
int32_t sir[MAX_N];
int main() {
	std::ifstream fin("cmlsc.in");
	std::ofstream fout("cmlsc.out");

	int32_t m, n;
	fin >> m >> n;
	for(int32_t i = 0; i != m; ++i)
		fin >> vec1[i];
	for(int32_t i = 0; i != n; ++i)
		fin >> vec2[i];
	
	dp[0][0] = vec1[0] == vec2[0];
	for(int32_t i = 1; i != n; ++i)
		if(vec1[0] == vec2[i]) {
			dp[0][i] = 1;
		} else {
			dp[0][i] = dp[0][i - 1];
		}
	for(int32_t i = 1; i != m; ++i)
		if(vec1[i] == vec2[0]) {
			dp[i][0] = 1;
		} else {
			dp[i][0] = dp[i - 1][0];
		}
	for(int32_t i = 1; i != m; ++i)
		for(int32_t j = 1; j != n; ++j)
			if(vec1[i] == vec2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			} else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
	int32_t row = m - 1, col = n - 1, top = 0;
	while(row != -1 && col != -1 && dp[row][col]) {
		if(vec1[row] == vec2[col]) {
			sir[top++] = vec1[row];
			--row;
			--col;
		} else if(!row) {
			--col;
		} else if(!col) {
			--row;
		} else if(dp[row - 1][col] > dp[row][col - 1]) {
			--row;
		} else {
			--col;
		}
	}
	fout << dp[m - 1][n - 1] << '\n';
	for(int32_t i = top - 1; i != -1; --i)
		fout << sir[i] << ' ';

	fin.close();
	fout.close();

	return 0;
}