Pagini recente » Profil KENJIRO | Cod sursa (job #2131033) | Cod sursa (job #1793537) | Cod sursa (job #1793546) | Cod sursa (job #1793547)
#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;
}