Pagini recente » Cod sursa (job #1220750) | Cod sursa (job #2599351) | Cod sursa (job #2659488)
#include <iostream>
#include <fstream>
#define NMAX 1025
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int x[NMAX], y[NMAX];
int N, M;
int DP[NMAX][NMAX];
void LCS(int i, int j ){
if( i == 0 || j == 0 ) return;
if( x[i] == y[j]){
LCS(i-1,j-1);
DP[i][j] = DP[i-1][j-1] + 1;
}
else{
LCS( i-1, j );
LCS( i, j-1 );
DP[i][j] = max(DP[i-1][j], DP[i][j-1] );
}
}
void Path(int i, int j){
if( !i || !j )return;
if( x[i] == y[j] ){
Path( i-1, j-1 );
fout << x[i] << ' ';
}
else{
if( DP[i-1][j] > DP[i][j-1] )Path( i-1, j );
else Path( i, j-1 );
}
}
void Solve(){
fin >> N >> M;
for( int i = 1; i <= N; ++i )
fin >> x[i];
for( int j = 1; j <= M; ++j )
fin >> y[j];
LCS(N,M);
/*for( int i = 1; i <= N; ++i ){
for( int j = 1; j <= M; ++j )
fout << DP[i][j] << ' ';
fout << '\n';
}*/
fout << DP[N][M] << '\n';
Path(N,M);
}
int main(){
Solve();
return 0;
}