Cod sursa(job #2166253)

Utilizator chioreanraulChiorean Raul chioreanraul Data 13 martie 2018 16:18:46
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

#define Nmax 1030
using namespace std;
int dp[Nmax][Nmax],n,m,i,j,a[Nmax],b[Nmax],rasp[Nmax],nsir;

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

int main()
{
    fin>>n>>m;
    for( i = 1; i<= n; i++ )
        fin>>a[ i ];
    for( i = 1; i <= m; i++ )
        fin>>b[ i ];
    for( i = 1; i <= n; i++ )
    {
        for( j = 1; j <= m; j++ )
        {
            if( a[ i ] == b[ j ] )
                dp[ i ][ j ] = 1 + dp [ i - 1 ][ j - 1 ];
            else
                dp[ i ][ j ] = max( dp [ i - 1][ j ], dp[ i ][ j - 1 ] );
        }
    }
    i = n; j = m;
    while( i > 0 and j > 0 )
    {
        if( a[ i ] ==  b[ j ] )
        {
            rasp[ ++nsir ] = a[ i ];
            i--;
            j--;
        }
        else if( dp[ i ][ j - 1 ] > dp[ i - 1 ][ j ])
                    j--;
             else
                i--;
    }
    fout<<nsir<<'\n';
    for( i = nsir; i > 0; i-- )
        fout<<rasp[ i ]<<" ";
    return 0;
}