Cod sursa(job #819219)

Utilizator YoYoxxIftimesei Ioan YoYoxx Data 18 noiembrie 2012 18:04:12
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
using namespace std;
ifstream in ("cmlsc.in");
ofstream out ("cmlsc.out");
int x[1025];
int x2[1025];
int mat[1025][1025];

void citire (int a,int b)
{
    int i,j;
    for (i=1;i<=a;i++)
    {
        in>>x[i];
    }
    for (i=1;i<=b;i++)
    {
        in>>x2[i];
    }
}


void rezolvare (int a,int b)
{
    int i,j;
    for (i=1;i<=a;i++)
    {
        for(j=1;j<=b;j++)
        {
            if (x[i]==x2[j]) mat[i][j]=mat[i-1][j-1]+1;
            else if (x[i]!=x2[j]) mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
        }
    }


}

int max(int a,int b)
{
    if (a>b) return a;
    if (b>a) return b;


}

int elemente (int a,int b)
{
    int g,ok=0,i,j;

    for (i=1;i<=a;i++)
    {
        for (j=1;j<=b;j++)
        {
            if (ok==0) {g=mat[i][j]; ok=1;}
            if (mat[i][j]>g)g=mat[i][j];
        }
    }
return g;
}

void afisare(int k,int h){

	if(mat[k][h]>0)
	{

            if(x[k]==x2[h])
            {
                afisare(k-1,h-1);
                out<<x[k]<<' ';
            }

            else
            {
                if (mat[k][h]==mat[k-1][h])
                afisare(k-1,h);
                else if (mat[k][h]==mat[k][h-1])
                afisare(k,h-1);
            }
	}
}


int main()
{
   int a,b,ok=0;
   in>>a>>b;
   if (a>b) ok=1;
   citire (a,b);
   rezolvare(a,b);
   out<<elemente(a,b)<<"\n";

   afisare (a,b);


return 0;
}