Cod sursa(job #1250727)

Utilizator alexutapristavu alexandra maria alexuta Data 28 octombrie 2014 14:19:53
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
using namespace std;
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int a[1025], b[1025], c[1025][1025], d[1024], i, j, k, m, n;

int main()
{
    f>>n>>m;
    for (i=1; i<=n; ++i) f>>a[i];
    for (i=1; i<=m; ++i) f>>b[i];

    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            if (a[i]==b[j]) c[i][j]=c[i-1][j-1]+1;
                else c[i][j]=max(c[i-1][j], c[i][j-1]);


    i=n;
    j=m;
    while (c[i][j])
    {
        while (c[i-1][j]==c[i][j]) --i;
        while (c[i][j-1]==c[i][j]) --j;
        ++k;
        d[k]=a[i];
        --i;
        --j;
    }
    g<<k<<'\n';
    for (i=k; i>0; --i) g<<d[i]<<' ';
    g.close();
    return 0;
}