Cod sursa(job #149632)

Utilizator sigridMaria Stanciu sigrid Data 5 martie 2008 22:12:52
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream.h>
#define dim 10//2//5
int a[dim],b[dim],c[dim*dim][2],p[dim],b2[dim];
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int main()
{int n,m;
f>>n>>m;
int i,j,cont=0;
for(i=1;i<=n;i++) f>>a[i];
for(j=1;j<=m;j++) f>>b[j];
f.close();

//completez c
for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
  {if(a[i]==b[j])
    {c[++cont][0]=i;
     c[cont][1]=j;
    }
  }

//cel mai lg subs. crescator
int max,max2;
b[1]=1;
for(i=2;i<=cont;i++)
 {max=0;j=0;
  for(j=1;j<i;j++)
   {if((c[j][0]<c[i][0])&&(c[j][1]<c[i][1])&&(b[j]>max)) {max=b[j];m=j;}
   }
  p[i]=m;
  b[i]=max+1;
 }
max=0;
for(i=1;i<=cont;i++)
 if(b[i]>max)
  {max=b[i];
   m=i;
  }
g<<max<<'\n';
i=1;
b2[i]=a[c[m][0]];
m=p[m];
max2=max;
max=max-1;
while(max)
{i++;
 b2[i]=a[c[m][0]];
 m=p[m];
 max--;
}
for(i=max2;i>=1;i--) g<<b2[i]<<" ";
//cout<<b2[1]<<" "<<b2[2]<<" ";
g<<'\n';
g.close();
return 0;
}