Cod sursa(job #2659488)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 16 octombrie 2020 20:54:04
Problema Cel mai lung subsir comun Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#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;
}