Cod sursa(job #2412330)

Utilizator federicisFedericis Alexandru federicis Data 22 aprilie 2019 07:13:57
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream in("cmlsc.in");
ofstream out("cmlsc.out");

int v1[1025],v2[1025],i,j,m,n,lungime[1025][1025],solutie[1025],nr;

int main()
{
 in>>m>>n;
 for(i=1;i<=m;i++)
 {
     in>>v1[i];
 }
 for(j=1;j<=n;j++)
 {
     in>>v2[j];
 }
 for(i=0;i<=m;i++)
 {
     for(j=0;j<=n;j++)
     {
         if(i==0||j==0)
         {
            lungime[i][j]=0;
         }
         else
         {
             if(v1[i]==v2[j])
             {
                 lungime[i][j]=lungime[i-1][j-1]+1;
             }
             else
             {
                 lungime[i][j]=max(lungime[i-1][j],lungime[i][j-1]);
             }
         }
     }
 }
 /*for(i=1;i<=m;i++)
 {
     for(j=1;j<=n;j++)
     {
         out<<lungime[i][j]<<" ";
     }
     out<<'\n';
 }*/ out<<lungime[m][n]<<'\n';
 nr=lungime[m][n]; i=m; j=n; ///cout<<v1[i]<<" "<<v2[j];
 while(nr)
 {
     if(v1[i]==v2[j])
     {
         solutie[nr]=v1[i]; cout<<"?";
         nr--;
         i--;
         j--;
     }
     else
     {
         if(lungime[i-1][j]>=lungime[i][j-1])
         {
             i--;
         }
         else
         {
             j--;
         }
     }
 }
 for(i=1;i<=lungime[m][n];i++)
 {
     out<<solutie[i]<<" ";
 }
    return 0;
}