Cod sursa(job #2233655)

Utilizator skoda888Alexandru Robert skoda888 Data 23 august 2018 20:11:38
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb

//Arhiva Educationala - 001. Cel mai lung subsir comun

#include <iostream>
#include <fstream>
#include <vector>

int main()
{
    std::ifstream in("cmlsc.in");
    std::ofstream out("cmlsc.out");

    int M; //numarul de elemente ale vect. A
    in >> M;
    int N; //numarul de elemente ale vect. B
    in >> N;

    //citirea elementelor vect. A
    int A[M];
    for(int i = 0; i < M; ++i){
        in >> A[i];
    }

    //citirea elementelor vect. B
    int B[N];
    for(int i = 0; i < N; ++i){
        in >> B[i];
    }

    //Voi utiliza programarea dinamica, metoda tabulara
    int DP_table[M + 2][N + 2] = {};
    for(int i = 1; i <= M; ++i){
        for(int j = 1; j <= N; ++j){
            if(A[i - 1] == B[j - 1]){
                DP_table[i][j] = DP_table[i - 1][j - 1] + 1;
            }
            else{
                DP_table[i][j] = std::max(DP_table[i][j - 1], DP_table[i - 1][j]);
            }
        }
    }

    out << DP_table[M][N] << '\n';

    int i = M;
    int j = N;

    std::vector<int> lcs;
    while(i > 0 && j > 0){
        if(A[i - 1] == B[j - 1]){
            lcs.push_back(A[i - 1]);
        }

        if(DP_table[i][j - 1] < DP_table[i - 1][j]){
            --i;
        }
        else{
            --j;
        }
    }

    for(int i = lcs.size() - 1; i >= 0; --i){
        out << lcs[i] << ' ';
    }
    return 0;
}