Cod sursa(job #1793547)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 31 octombrie 2016 10:06:58
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>

#define MAX_N 1025

struct Cell
{
	int val = 0;
};

FILE* fin;
FILE* fout;

int m, n;

int aValues[MAX_N];
int bValues[MAX_N];

Cell matrix[MAX_N][MAX_N];

unsigned short solution[MAX_N];
int solLength = 0;

void LoadFiles()
{
	fin = fopen("cmlsc.in", "r");
	fout = fopen("cmlsc.out", "w");
}

void Init()
{
	LoadFiles();
}

void Read()
{
	fscanf(fin, "%d %d", &m, &n);

	for (int i = 1;i <= m;i++)
	{
		fscanf(fin, "%d", &aValues[i]);
	}

	for (int i = 1;i <= n;i++)
	{
		fscanf(fin, "%d", &bValues[i]);
	}
}

int Max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}

void CreateSolution()
{
	solLength = 0;

	for (int i = m, j = n;i;)
	{
		if (aValues[i] == bValues[j])
		{
			solution[solLength++] = aValues[i];
			i--;
			j--;
		}
		else
		{
			if (matrix[i - 1][j].val < matrix[i][j - 1].val)
			{
				j--;
			}
			else
			{
				i--;
			}
		}
	}
}

void Solve()
{
	for (int i = 1;i <= m;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			if (aValues[i] == bValues[j])
			{
				matrix[i][j].val = matrix[i - 1][j - 1].val + 1;
			}
			else
			{
				matrix[i][j].val = Max(matrix[i - 1][j].val, matrix[i][j - 1].val);
			}
		}
	}

	CreateSolution();
}

void Write1()
{
	fprintf(fout, "%d\n", solLength);
}

void Write2()
{
	for (int i = solLength - 1;i >= 0;i--)
	{
		fprintf(fout, "%d ", solution[i]);
	}
}

void Write()
{
	Write1();
	Write2();
}

void CloseFiles()
{
	fclose(fin);
	fclose(fout);
}

void Terminate()
{
	CloseFiles();
}

int main(void)
{
	Init();
	Read();
	Solve();
	Write();
	Terminate();

	return 0;
}