Cod sursa(job #2233034)

Utilizator georgiana.dianaOjoc Georgiana Diana georgiana.diana Data 21 august 2018 22:51:15
Problema Cel mai lung subsir comun Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>

using namespace std;

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

unsigned mat[1025][1025];

int main()
{
    unsigned A[1025], B[1025], M, N, i, j, sol[1025], k = 0;
    f >> M >> N;
    for (i = 1; i <= M; i++)
        f >> A[i];
    for (j = 1; j <= N; j++)
        f >> B[j];
    f.close();
    for (i = 0; i <= M; i++)
        mat[i][0] = 0;
    for (j = 1; j <= N; j++)
        mat[0][j] = 0;
    for (i = 1; i <= M; i++)
        for (j = 1; j <= N; j++)
            if (A[i] == B[j])
                mat[i][j] = mat[i-1][j-1] + 1;
                else
                    mat[i][j] = max(mat[i][j-1], mat[i-1][j]);
    for (i = 0; i <= M; i++)
    {
        for (j = 0; j <= N; j++)
            cout << mat[i][j] << ' ';
        cout << endl;
    }
    i = M;
    j = N;
    while (i && j)
        if (A[i] == B[j])
        {
            sol[++k] = A[i];
            i--;
            j--;
        }
            else
                if (mat[i-1][j] > mat[i][j-1])
                    i--;
                    else
                        j--;
    g << mat[M][N] << endl;
    for (i = k; i; i--)
        g << sol[i] << ' ';
    g.close();
    return 0;
}