Cod sursa(job #1477252)

Utilizator gerd13David Gergely gerd13 Data 25 august 2015 19:38:14
Problema Cel mai lung subsir comun Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<bits/stdc++.h>

using namespace std ;
const short NMAX  = 1024 ;
ifstream fin("cmlsc.in") ;
ofstream fout("cmlsc.out") ;
short N, M, BEST, D[NMAX][NMAX], A[NMAX], B[NMAX], sol[NMAX] ;

int main()
{
    fin >> M >> N ;

    for(short i = 1 ; i <= M ; ++ i)
        fin >> A[i] ;

    for(short i = 1 ; i <= N ; ++ i)
        fin >> B[i] ;

    for(short i = 1 ; i <= M ; ++ i)
        for(short j = 1 ; j <= N ; ++ j)
            if(A[i] == B[j])
                D[i][j] = D[i - 1][j - 1] + 1;
            else D[i][j] = max(D[i - 1][j], D[i][j - 1]) ;


    for(short i = M, j = N; i;)
        if(A[i] == B[j])
        {
            sol[++ BEST] = i;
            -- i  ; -- j  ;
        }
        else if(D[i][j - 1] < D[i - 1][j])
            -- i ;
        else -- j ;

    fout << BEST << '\n';

    for(short i = BEST; i ; i --)
        fout << A[sol[i]] << ' ' ;

    fout << '\n' ;
    fin.close() ;
    fout.close() ;
    return 0 ;
}