Cod sursa(job #2263132)

Utilizator sidorencuoanaSidorencu Oana Alexandra sidorencuoana Data 18 octombrie 2018 11:31:25
Problema Cel mai lung subsir comun Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#define MAX 1024

using namespace std;


int M,N,A[MAX],B[1024],mat[1024][1024],sir[1024];

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

void Din (int M,int N)
{
    int i,j;
    for(i=1;i<=M;i++)
    for(j=1;j<=N;j++)
     if(A[i]==B[j])
     mat[i][j]=1+mat[i-1][j-1];
     else
     mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
     g<<mat[M][N]<<endl;
     g<<endl;
     /*for(i=1;i<=M;i++)
      {for(j=1;j<=N;j++)
        g<<mat[i][j];
        g<<endl;
      }*/

}

void Sir(int M,int N)
{
    int i=M,j=N,k=0;
    while(i!=0 || j!=0)
    {if(A[i]==B[j])
    {sir[++k]=A[i];
    i--;
    j--;}
    else
    if(mat[i-1][j]<mat[i][j-1])
    j--;
    else
    i--;
    }
    for(i=k;i>=1;i--)
    g<<sir[i]<<" ";


}
int main()
{int i;
    f>>M>>N;
    for(i=1;i<=M;i++)
    f>>A[i];
    for(i=1;i<=N;i++)
    f>>B[i];
    Din(M,N);
    Sir(M,N);
    return 0;
}