Cod sursa(job #903604)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 1 martie 2013 23:12:49
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>

using namespace std;

int L1, L2, i, j;

int A[1030], B[1030];

int D[1030][1030];

bool max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{

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

    scanf("%d %d", &L1, &L2);

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

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

    D[0][0] = 0;
/*
    for(i=1;i<=L1;++i)
        cout<<A[i]<<" ";
    cout<<"\n";
    for(i=1;i<=L2;++i)
        cout<<B[i]<<" ";
    cout<<"\n";
*/
    for(i=1;i<=L1;++i)
        for(j=1;j<=L2;++j)
            if(A[i] == B[j])
                D[i][j] = 1 + D[i-1][j-1];
            else
                D[i][j] = max(D[i-1][j], D[i][j-1]);
/*
    for(i=1;i<=L1;++i)
    {
        for(j=1;j<=L2;++j)
            cout<<D[i][j]<<" ";
        cout<<"\n";
    }*/
    int ok = 0, lmax = 0, REZ[1030];
    for(i=1;i<=L1;++i)
        for(j=1;j<=L2;++j)
        {
            if(D[i][j] != ok)
            {

                ok = D[i][j];

                REZ[++lmax] = A[i];
            }

        }

    cout<<lmax<<"\n";
    for(i=1;i<=lmax;++i)
        cout<<REZ[i]<<" ";
    return 0;
}