Pagini recente » Cod sursa (job #3362225) | Cod sursa (job #3361785) | Cod sursa (job #3362237)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int lscRec(const vector<int>& A, const vector<int>& B, int m, int n, vector<vector<int>>& memo){
if(m == 0 || n == 0) return 0;
if(memo[m][n] != -1) return memo[m][n];
if(A[m-1] == B[n-1]){
return memo[m][n] = 1 + lscRec(A, B, m-1, n-1, memo);
}
return memo[m][n] = max(lscRec(A, B, m, n-1, memo), lscRec(A, B, m-1, n, memo));
}
int main(){
int m, n;
fin >> m >> n;
vector<int> A(m), B(n);
for(int i = 0; i < m; i++){
fin >> A[i];
}
for(int i = 0; i < n; i++){
fin >> B[i];
}
vector<vector<int>> memo(m+1, vector<int>(n+1, -1));
int lungime = lscRec(A, B, m, n, memo);
fout << lungime << '\n';
vector<int> C;
int i = m, j = n;
while (i > 0 && j > 0) {
if (A[i - 1] == B[j - 1]) {
C.push_back(A[i - 1]);
i--;
j--;
}
else if (memo[i - 1][j] >= memo[i][j - 1]) {
i--;
} else {
j--;
}
}
reverse(C.begin(), C.end());
for (int val : C) {
fout << val << " ";
}
}