Cod sursa(job #2485366)

Utilizator MCnitzzNita Sebastian MCnitzz Data 1 noiembrie 2019 13:52:37
Problema Cel mai lung subsir comun Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;
#define max(a,b) ((a>b)?a:b)

ifstream in("cmlsc.in");
ofstream out("cmlsc.out");
int i,j,N,M,A[1025],B[1025],Z[1025][1025],C[1025],nr=0;

int main()
{
    in>>N>>M;
    for(i=1;i<=N;i++)in>>A[i];
    for(i=1;i<=M;i++)in>>B[i];
    for(i=1;i<=M;++i)
        for(j=1;j<=N;++j)
           {
               if(A[i]==B[j]){

                Z[i][j]=1+Z[i-1][j-1];

               }else
               {
                   Z[i][j]=max(Z[i-1][j],Z[i][j-1]);

               }
            }
      for(i=N,j=M;i,j;)
     {
         if(A[i]==B[j])
         {
             C[++nr]=A[i],i--,j--;
         }else
         if(Z[i-1][j]>Z[i][j-1]){i--;}else{j--;}

     }
     out<<nr<<"\n";
     for(i=nr;i>=1;i--)
        out<<C[i]<<" ";

    return 0;
}