Cod sursa(job #1556403)

Utilizator georgeliviuPereteanu George georgeliviu Data 24 decembrie 2015 18:36:24
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int d[1030][1030] , a[1030] , b[1030] ;

void scriere ( int x , int y )
{
    if( x > 0  and y > 0 )
    {
        if( a[x] == b[y] )
        {
            scriere( x-1 , y-1 );
            printf("%d ",a[x]);
        }
        else
        {
            if( d[x-1][y] > d[x][y-1] )
                scriere( x - 1 , y ) ;
            else
                scriere( x , y - 1  ) ;
        }
    }
}

int main()
{
    freopen("cmscl.in","r",stdin);
    freopen("cmscl.out","w",stdout);
    int n , m ;
    scanf("%d %d",&n,&m);
    for ( int i = 1 ; i <= n ; i++ )
    {
        scanf("%d ",&a[i]);
    }
    for ( int i = 1 ; i <= m ; i++ )
    {
        scanf("%d ",&b[i]);
    }
    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-1][j] , d[i][j-1] ) ;
        }
    }
    printf("%d\n",d[n][m]);
    scriere(n,m);
    return 0 ;
}