Cod sursa(job #809274)

Utilizator popacamilpopa camil popacamil Data 8 noiembrie 2012 08:36:12
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>

using namespace std;

int a[100],b[100],n,i,j,m,LCS[100][100],OP[100][100];

int main(){

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


    scanf("%d%d",&n,&m);

    for(i=1;i<=n;++i){

        scanf("%d",&a[i]);

    }

    for(j=1;j<=m;++j){

        scanf("%d",&b[j]);

    }

    for(i=n;i>=1;--i){

        for(j=m;j>=1;--j){

            if(a[i]==b[j]){

                LCS[i][j]=1+LCS[i+1][j+1];

                OP[i][j]=1;

            }
            else{

                if(a[i]!=b[j]){

                    if(LCS[i+1][j]>LCS[i][j+1]){

                        LCS[i][j]=LCS[i+1][j];

                        OP[i][j]=2;
                    }
                    else{

                        LCS[i][j]=LCS[i][j+1];

                        OP[i][j]=3;

                    }

                }

            }

        }

    }

    printf("%d\n",LCS[1][1]);

    i=1;
    j=1;
    while(OP[i][j]!=0){

        if(OP[i][j]==1){
            printf("%d ",a[i]);
            ++i;
            ++j;
        }
        else{

            if(OP[i][j]==2){

                ++i;

            }

            else{ ++j;}

        }

    }
    return 0;
}