Cod sursa(job #2604348)

Utilizator michael_blazemihai mihai michael_blaze Data 22 aprilie 2020 15:03:48
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
	
#include <algorithm>
	
 
	
#define MAX 1030
	
 
	
using namespace std;
	
 
	
ifstream fin ("cmlsc.in");
	
ofstream fout("cmlsc.out");
	
 
	
int n, m;
	
int a[MAX], b[MAX];
	
int sir[MAX];
	
int sol[MAX];
	
int len;
	
 
	
bool subsir(int nivel) {
	
	int i = 1, j = 1;
	
	for (;i <= nivel and j <= m;i ++)
	
		for(;j <= m and b[j ++] != sir[i];);
	j --;
	return j <= m;
	
}
	
void backtracking(int k, int nivel) {
	
	int i = 1;
	
	if (k == n + 1) {
	
		if (subsir(nivel)) {
	
			if (nivel > len) {
	
				len = nivel;
	
				for (i = 1;i <= nivel;i ++)
	
					sol[i] = sir[i];
	
			}	
	
		}
	
		return;
	
	} 
	
 
	
	backtracking(k + 1, nivel);
	
	sir[nivel + 1] = a[k];
	
	backtracking(k + 1, nivel + 1);
	
}
	
int main() {
	
	fin >> n >> m;
	
	for (int i = 1;i <= n;i ++)
	
		fin >> a[i];
	
	for (int i = 1;i <= m;i ++)
	
		fin >> b[i];
	
 
	
	backtracking(1, 0);
	
 
	
	fout << len << '\n';
	
	for (int i = 1;i <= len;i ++)
	
		fout << sol[i] << ' ';
	
	return 0;
	
}