Cod sursa(job #2308936)

Utilizator CoroloHorjea Cosmin Corolo Data 28 decembrie 2018 01:46:21
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>

#define max(a,b) ((a>b) ? a : b)

using namespace std;

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

int main(){
      int n,m,i,j,a[100],b[100],c[100][100];
      f>>n>>m;
      
      for(i = 1; i <= n; i++)
            f>>a[i];
      for(i = 1; i <= m; i++)
            f>>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][j-1],c[i-1][j]);
            }
      }
      g<<c[n][m]<<"\n";
      int l=c[n][m];
      int aux[100];
      i=n;j=m;
      while(i && j){
      
                 if(a[i]==b[j]){
                       aux[--l]=a[i];
                       i--;
                       j--;
                       }
                 else{
                       if(c[i-1][j]<c[i][j-1])--j;
                       else --i;
                 }
            
      }
      for(i=0;i<c[n][m];i++)
            g<<aux[i]<<" ";
      f.close();
      g.close();
}