Cod sursa(job #1780376)

Utilizator MirceaTMircea Timpuriu MirceaT Data 16 octombrie 2016 08:14:15
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int x,y,a,b,c=0,d=0,i,j;
    cin>>x>>y;
    int m[x][y]={},v[x]={},v1[y]={},v2[1024]={};
    for(i=0;i<x;++i)
    {
        cin>>v[i];
    }
    for(j=0;j<y;++j)
    {
        cin>>v1[j];
    }
    if(v[0]==v1[0])
    {
        m[0][0]=1;
    }
    else
    {
        m[0][0]=0;
    }

    for(i=1;i<x;++i)
    {
        if(v[i]==v1[0])
        {
            m[i][0]=m[i-1][0]+1;
        }
        else
        {
            m[i][0]=m[i-1][0];
        }
    }
     for(j=1;j<y;++j)
     {
        if(v[0]==v1[j])
        {
            m[0][j]=m[0][j-1]+1;
        }
        else
        {
            m[0][j]=m[0][j-1];
        }
     }
     for(i=1;i<x;++i)
     {
        for(j=1;j<y;++j)
        {
            if(v[i]==v1[j])
            {
                m[i][j]=m[i-1][j-1]+1;
            }
            else
            {
                m[i][j]=max(m[i-1][j],m[i][j-1]);
            }
        }
     }
     cout<<m[x-1][y-1]<<endl;
     a=x-1;
     b=y-1;
     while(m[a][b])
     {
        if(m[a][b]==m[a-1][b])
        {
            a--;
        }
        else
        {
            v2[c]=v[a];
            c++;
            a--;
            b--;
        }
    }
    while(c)
    {
        cout<<v2[c-1]<<" ";
        c--;
        d++;
    }
}