Cod sursa(job #1449245)

Utilizator gerd13David Gergely gerd13 Data 9 iunie 2015 08:29:33
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std ;


const int NMAX = 1024 ;

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

int N, M, A[NMAX], B[NMAX], D[NMAX][NMAX], best, sir[NMAX];


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


    for(int i = 1 ; i <= N ; ++ i )
        fin >> A[i] ;

    for(int j = 1 ; j <= M ; ++ j)
        fin >> B[j] ;

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



            for(int i = N, j = M; i;)
            if(A[i] == B[j])
            {

                sir[++ best] = A[i] ;
                -- i ;
                -- j ;

            }
            else if(D[i - 1][j] < D[i][j - 1])
                -- j;

            else -- i ;

            fout << best << '\n' ;


            for(int i = best ; i ; i --)
                fout << sir[i] << ' ' ;

    fin.close() ;
    fout.close() ;
    return  0 ;
}