Cod sursa(job #545400)

Utilizator shnakoVlad Schnakovszki shnako Data 3 martie 2011 11:41:25
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#define LIM 1025
FILE *f=fopen("cmlsc.in", "r"), *g=fopen("cmlsc.out", "w");
int i, j, m, n, t=1, a[LIM], b[LIM], v[LIM][LIM], rez[LIM];

void citeste()
{
	fscanf(f, "%d%d", &m, &n);
	for (i=1;i<=m;i++)
		fscanf(f, "%d", &a[i]);
	for (i=1;i<=n;i++)
		fscanf(f, "%d", &b[i]);
}

void matrice()
{
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			if (v[i-1][j]>v[i][j-1])
				v[i][j]=v[i-1][j];
			else
				v[i][j]=v[i][j-1];
			if (a[i]==b[j])
				v[i][j]++;
		}
}

void reconstituie(int m, int n)
{
	if (v[m-1][n]||v[m][n-1])
	{
		if (v[m-1][n]<v[m][n]&&v[m][n-1]<v[m][n])
			rez[t++]=a[m];
		if (v[m-1][n]>v[m][n-1])
			reconstituie(m-1, n);
		else
			reconstituie(m, n-1);
	}
	else
		rez[t]=a[m];
}

void tipareste()
{
	fprintf(g, "%d\n", v[m][n]);
	for (i=t;i>0;i--)
		fprintf(g, "%d ", rez[i]);
	fclose(f);
	fclose(g);
}

int main()
{
	citeste();
	matrice();
	reconstituie(m, n);
	tipareste();
	return 0;
}