Cod sursa(job #146733)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 2 martie 2008 01:42:05
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>

int N[1024],M[1024],R[1024];
short C[1024][1024];

int main ()
{
    int i,j,n,m,r;
    freopen ( "cmlsc.in" , "r" , stdin );
    scanf ( "%d %d" , &n , &m );
    for ( i=0 ; i<n ; i++ )
    {
        scanf ( "%d" , &r );
        N[i]=r;
    }
    for ( i=0 ; i<m ; i++ )
    {
        scanf ( "%d" , &r );
        M[i]=r;
    }
    fclose ( stdin );

    for (r=i=0 ; i<n ; i++)
    {
        r = (r || (N[i]==M[0]))?(1):(0);
        C[i][0]=r;
    }

    for (r=i=0 ; i<m ; i++)
    {
        r= (r|| (N[0]==M[i]))?(1):(0);
        C[0][i]=r;
    }
    for ( i=1 ; i<n ; i++ )
        for ( j=1 ; j<m ; j++ )
            if (N[i]==M[j]) C[i][j]=C[i-1][j-1]+1;
            else C[i][j]=(C[i-1][j]>C[i][j-1])?C[i-1][j]:C[i][j-1];

    int mm=m;

    for ( i=n-1,r=C[n-1][m-1] ; i>=0 ; i-- )
        for ( j=mm-1 ; j>=0 ; j-- )
            if (C[i][j]==r && N[i]==M[j])
            {
                R[r-1]=M[j];
                mm = j;
                r--;
                i--;
            }
    freopen ( "cmlsc.out" , "w" , stdout );
    printf ( "%d\n" , C[n-1][m-1] );
    for ( i=0 ; i<C[n-1][m-1]-1 ; i++ ) printf ( "%d " , R[i] );
    printf ( "%d\n" , R[C[n-1][m-1]-1] );
    fclose ( stdout );
}