Pagini recente » Cod sursa (job #2426795) | Cod sursa (job #761817) | Cod sursa (job #2873929) | Cod sursa (job #1443236) | Cod sursa (job #2405777)
#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i = a; i < b; i++)
using namespace std;
const int MaxN = 1024;
int M, N, A[MaxN], B[MaxN], C[MaxN][MaxN], L[MaxN];
int dp(int m, int n) {
if (m < 0 || n < 0) {
return 0;
}
if (C[m][n] != -1) { return C[m][n]; }
if (A[m] == B[n]) {
C[m][n] = dp(m-1, n-1) + 1;
// L[C[m][n]-1] = A[m];
} else {
C[m][n] = max(dp(m-1, n), dp(m, n-1));
}
return C[m][n];
}
int main(void) {
freopen("cmlsc.in", "r", stdin);
freopen("cmlsc.out", "w", stdout);
cin >> M >> N;
rep(i, M) {
rep(j, N) {
C[i][j] = -1;
}
}
rep(i, M) { cin >> A[i]; }
rep(i, N) { cin >> B[i]; }
int result = dp(M-1, N-1);
cout << result << endl;
int m = M-1, n = N-1, k = result-1;
while(m > -1 && n > -1) {
if (A[m] == B[n]) {
L[k] = A[m];
k--;
m--;
n--;
} else {
if (C[m][n] == C[m-1][n])
m--;
else
n--;
}
}
rep(i, result) {
cout << L[i] << ' ';
}
cout << endl;
return 0;
}