Cod sursa(job #293873)

Utilizator robigiirimias robert robigi Data 2 aprilie 2009 09:32:58
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream.h>

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

int n, v[1024], w[1024], m, mat[1024][1024], sir[1024], aux;

void read()
{    f >> n >> m;
     for (int i=1; i<=n; i++)
	 f >> v[i];
     for (int j=1; j<=m; j++)
	 f >> w[i];
}

void program()
{    for (int i=1; i<=n; i++)
	 for (int j=1; j<=m; j++)
	     if (v[i]==w[i])
		mat[i][j]++;
	     else if (mat[i-1][j]>mat[i][j-1]) mat[i][j]=mat[i-1][j];
		  else mat[i][j]=mat[i][j-1];
     int ii=n;
     int jj=m;
     while (ii && jj)
     {     if (v[ii]==w[jj])
	   {  sir[++aux]=v[ii];
	      ii--;
	      jj--;
	   }
	   else if (mat[ii][jj-1]>mat[ii-1][jj])
		   jj--;
		else ii--;
     }
     g << aux;
     for (int k=1; k>=1; k++)
	 g << v[k] << " ";
}

int main()
{   read();
    program();
    return 0;
}