Cod sursa(job #1805770)

Utilizator razvan99hHorhat Razvan razvan99h Data 14 noiembrie 2016 13:02:27
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("cmlsc.in");

ofstream fout("cmlsc.out");

int n, m, a[1040], b[1040], i, j, rez[1040], rezl, nr, c[1040][1040];

int main()

{

    fin>>n>>m;

    for(i=1;i<=n;i++)

        fin>>a[i];

    for(i=1;i<=m;i++)

        fin>>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]);

        }

    /*for(i=1;i<=n;i++)

        {for(j=1;j<=m;j++)

            cout<<c[i][j]<<' '; cout<<endl;}*/

 

    i=n; j=m;

    while(i>0 && j>0)

    {

        if(a[i]==b[j])//le adaugam la solutie

        {

            rezl++;

            rez[rezl]=a[i];

            i--; j--;

        }

        else

        {   if(c[i-1][j]>c[i][j-1])

                 i--;

             else j--;

        }

    }

    fout<<c[n][m]<<'\n';

    for(i=rezl;i>=1;i--)

        fout<<rez[i]<<' ';

    return 0;

}