Cod sursa(job #1778498)

Utilizator lucian2015blaugranadevil lucian2015 Data 13 octombrie 2016 20:51:45
Problema Cel mai lung subsir comun Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;

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

#define maxim(a, b) ((a > b) ? a : b)
int m, n, a[1025], b[1025], d[1025][1025], sir[1025],bst;

int main()
{  int i, j;
f>>m>>n;
  for(i=1;i<=m;i++)
    f>>a[i];
  for(i=1;i<=n;i++)
    f>>b[i];
  for(i=1;i<=m;i++)
    for(j=1;j<=m;j++)
      if(a[i]==b[j])
      d[i][j]=1+d[i-1][j-1];
  else
      d[i][j]=maxim(d[i-1][j],d[i][j-1]);

   for(i=m,j=n;i>=1;)
     if(a[i]==b[j])
       sir[++bst]=a[i],--i,--j;
   else if(d[i-1][j]<d[i][j-1])
      --j;
     else
        --i;
     g<<bst<<'\n';
     for(i=bst;i>=1;i--)
        g<<sir[i]<<' ';

    return 0;
}