Cod sursa(job #790053)

Utilizator legendary28Cornescu Mihail legendary28 Data 20 septembrie 2012 06:06:00
Problema Cel mai lung subsir comun Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>

#define Nmax 1024
#define MAX(x,y) (x>y?x:y);

int M,N,A[Nmax],B[Nmax],D[Nmax][Nmax],i,j, S[Nmax],l;

int main()
{
    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);

    scanf("%d%d",&M,&N);
    for(i=1;i<=M;i++)
        scanf("%d",&A[i]);
    for(i=1;i<=N;i++)
        scanf("%d",&B[i]);

    for(i=1;i<=M;i++)
        for(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(i=1;i<=M;i++)
    {
        for(j=1;j<=N;j++)
            printf("%d ",D[i][j]);
        printf("\n");

    }

    i=M;
    j=N;
    while(D[i][j])
    {
        if(D[i][j]>D[i-1][j-1])
        {
            S[++l]=A[i];
            i--;j--;
        }
        else if(D[i-1][j]>=D[i][j-1])
            i--;
        else j--;
    }

    for(;l;l--)
    {
        printf("%d ",S[l]);
    }

    return 0;
}