Cod sursa(job #1780513)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 16 octombrie 2016 12:25:37
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
 
int m[1030][1030],v[1030],v1[1030],v2[1030];
 
int main()
{
    int x,y,a,b,c=0,d=0,i,j;
    ifstream fin ("cmlsc.in");
    ofstream fout ("cmlsc.out");
    fin>>x>>y;
 
    for(i=1;i<=x;++i)
    {
        fin>>v[i];
    }
    for(j=1;j<=y;++j)
    {
        fin>>v1[j];
    }
        if(v[1]==v1[1])
    {
        m[1][1]=1;
    }
    else
    {
        m[1][1]=0;
    }
     for(i=2;i<=x;++i)
    {
        if(v[i]==v1[1])
        {
            m[i][1]=1;
        }
        else
        {
            m[i][1]=m[i-1][1];
        }
    }
     for(j=2;j<=y;++j)
    {
        if(v[1]==v1[j])
        {
            m[1][j]=1;
        }
        else
        {
            m[1][j]=m[1][j-1];
        }
    }
 
 
     for(i=2;i<=x;++i)
     {
        for(j=2;j<=y;++j)
        {
            m[i][j]=max(m[i-1][j],m[i][j-1]);
            if(v[i]==v1[j])
            {
                m[i][j]=max(m[i][j],m[i-1][j-1]+1);
            }
        }
     }
     fout<<m[x][y]<<endl;
     a=x;
     b=y;
     while(m[a][b])
     {
        if(v[a]==v1[b] && m[a][b]==m[a-1][b-1]+1)
        {
            v2[c]=v[a];
            c++;
            a--;
            b--;
        }
        else if (m[a-1][b]< m[a][b-1])
        {
           b--;
        }
        else
        {
            a--;
        }
    }
    while(c)
    {
        fout<<v2[c-1]<<" ";
        c--;
    }
}