Cod sursa(job #1320407)

Utilizator superman_01Avramescu Cristian superman_01 Data 17 ianuarie 2015 22:53:21
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 1025

using namespace std;

ifstream in ( "cmlsc.in" );
ofstream out ( "cmlsc.out" );


int DP[NMAX][NMAX];
int N , M , A[NMAX] , B [NMAX] ;
vector < int > Sol;

int main ( void ){

   int i , j ;
   in >> N >> M ;
   for ( i = 1 ; i <= N ; ++i )
      in >> A[i];
   for ( j = 1 ; j <= M ; ++j )
       in >> B [j] ;
   for ( i = 1 ; i <= N ; ++i )
       for ( j = 1 ; j <= M  ; ++j )
          if ( A[i] == B[j] )
            DP[i][j] = max ( DP[i][j],DP[i-1][j-1] + 1 );
          else DP[i][j] = max ( DP[i-1][j] , DP[i][j-1]);

  out <<DP[N][M] << "\n";

  for ( i = N , j = M ; i > 0 and j > 0 ; )
         if ( A[i] == B[j] )
           Sol.push_back(A[i]) , --i , --j;
        else if ( DP[i-1][j]> DP[i][j-1])
        --i;
        else --j;

   reverse(Sol.begin(), Sol.end());

   for ( vector<int>::iterator it = Sol.begin() ; it != Sol.end() ; ++it )
           out << *it << " ";

  return 0  ;
}