Cod sursa(job #1417817)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 11 aprilie 2015 01:19:06
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>

using namespace std;

fstream in("cmlsc.in",ios::in);
fstream out("cmlsc.out",ios::out);

int maxim(int,int); // functie care returneaza max a 2 nr

int main()
{
    int a[1025],b[1025],c[1026][1026],i,j,n,m,d[1025],k=0;
    in>>n>>m;

    for(i=0;i<n;i++)
    {
        c[i][0]=0;
        in>>a[i];
    }                       //scriete vector 1 si initilizare prima inie si coloana ca nula

    for(i=0;i<m;i++)
    {
        c[0][i]=0;
        in>>b[i];
    }                        //scriere vector 2

    for(i=1;i<=n;i++)       //formarea tabelului de referinte
        for(j=1;j<=m;j++)
        {
            if(a[i-1]==b[j-1])
                c[i][j]=maxim(c[i-1][j],c[i][j-1])+1;
            else
                c[i][j]=maxim(c[i-1][j],c[i][j-1]);
        }

    i=n;
    j=m;
    while(i>0&&j>0)
    {
        if((c[i-1][j]==c[i][j-1])&&c[i][j]>maxim(c[i-1][j],c[i][j-1]))
        {
            i--;
            j--;
            d[k++]=a[i];
        }
        else if(c[i][j-1]<=c[i-1][j])
            i--;
        else if(c[i-1][j]<c[i][j-1])
            j--;
    }

    out<<c[n][m]<<endl;
    for(i=k-1;i>=0;i--)
        out<<d[i]<<" ";



    return 0;
}


int maxim(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}