Pagini recente » Cod sursa (job #2262901) | Cod sursa (job #1169475) | Monitorul de evaluare | Cod sursa (job #1581416) | Cod sursa (job #2468989)
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
#define max(a, b) ( a > b ? a : b )
int main() {
ifstream in("cmlsc.in");
ofstream out("cmlsc.out");
int m, n;
in>>m>>n;
int a[m + 2], b[n + 2];
for(int i = 1; i <= m; i++)
in>>a[i];
for(int i = 1; i <= n; i++)
in>>b[i];
int arr[n + 2][m + 2];
for(int i = 0; i <= n; i++)
arr[i][0] = 0;
for(int i = 0; i <= m; i++)
arr[0][i] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[j] == b[i]){
arr[i][j] = 1 + arr[i - 1][j - 1];
} else {
arr[i][j] = max(arr[i][j - 1], arr[i - 1][j]);
}
}
}
out<<arr[n][m]<<"\n";
int sir[1026];
int index = -1;
while(n >= 1 || m >= 1){
int i = n, j = m;
if(a[j] == b[i]){
sir[++index] = a[j];
m--,n--;
} else {
if(arr[i][j - 1] > arr[i - 1][j]){
m--;
} else {
n--;
}
}
}
for(int i = index; i >= 0; i--){
out<<sir[i]<<" ";
}
return 0;
}