Cod sursa(job #143560)

Utilizator MciprianMMciprianM MciprianM Data 26 februarie 2008 17:40:39
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
using namespace std;
int a[1030][1030], x[1030],y[1030],m,n;
int b[1030][1030];
ofstream g("cmlsc.out");
void CMLSC(){
  int i, j;
  //a si b au valori nule
  for(i=1;i<=m;i++)
    for(j=1;j<=n;j++){
      if(x[i]==x[j]) 
        a[i][j]=a[i-1][j-1]+1;
      else if(a[i-1][j]>=a[i][j-1]){
             a[i][j]=a[i-1][j];
             b[i][j]=1;
           } 
           else {
             a[i][j]=a[i][j-1];
             b[i][j]=-1;
           } 
    }
}
void SCRIE(int i, int j){
  if(i&j){
    if(b[i][j]==0){
      SCRIE(i-1,j-1);
      g<<x[i]<<' ';
    }
    else if(b[i][j]==1)
           SCRIE(i-1,j);
         else SCRIE(i,j-1);
         
  } 
  else  return;
}
int main(){
  int i, j;
  ifstream f("cmlsc.in");
  f>>m>>n;
  for(i=1;i<=m;i++)
    f>>x[i];
  for(j=1;j<=n;j++)
    f>>y[i];
  f.close();
  CMLSC();
  g<<a[m][n]<<'\n';
  SCRIE(m,n);
  g<<'\n';
  g.close();
  return 0;
}