Cod sursa(job #1835190)

Utilizator AndreeaAmzaAndreea Amza AndreeaAmza Data 26 decembrie 2016 15:25:57
Problema Cel mai lung subsir comun Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("cmlsc.in");
ofstream g ("cmlsc.out");
int i,j,m[1001][1001],n,n2,a[1001],b[1001],sir[1001],bst;
int main()
{
    f>>n>>n2;
    for(i=1;i<=n;i++)
        f>>a[i];
    for(i=1;i<=n2;i++)
        f>>b[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n2;j++)
        if(a[i]==b[j]) m[i][j]=m[i-1][j-1]+1;
        else if(m[i-1][j]>m[i][j-1]) m[i][j]=m[i-1][j];
             else m[i][j]=m[i][j-1];
    //for(i=1;i<=n;i++)
    //{
      //  for(j=1;j<=n2;j++)
        //    cout<<m[i][j]<<" ";
        //cout<<endl;
    //}

    for(i=n,j=n2;i;)
        {
            if(a[i]==b[j]) {sir[bst++]=a[i];
                            i--;
                            j--;
                            }
            else if(m[i-1][j]<m[i][j-1])j--;
            else i--;
        }
    g<<bst<<endl;
    for(i=bst-1;i>=0;i--)
        g<<sir[i]<<" ";
    return 0;
}