Cod sursa(job #2695167)

Utilizator obleacmihaiObleac Mihai obleacmihai Data 11 ianuarie 2021 23:04:52
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int maxim(int a, int b) {
    return (a < b) ? b : a;
}
int main() {
    int n, m;

    fin >> n >> m;
    int x[10], y[10], b[10][10];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            b[i][j] = 0;
    for (int i = 1; i <= n; i++)
        fin >> x[i];
    for (int i = 1; i <= m; i++)
        fin >> y[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (x[i] == y[j])
                b[i][j] = b[i - 1][j - 1] + 1;
            else
                b[i][j] = maxim(b[i - 1][j], b[i][j - 1]);

    fout << b[n][m];

    int s = b[n][m];
    int sol[10];
    int i = n, j = m;
    while (s != 0) {
        if (x[i] == y[j])
            sol[s] = x[i], i--, j--, s--;
        else
            if (b[i][j - 1] < b[i - 1][j])
                j--; else
                i--;
    }

    fout << '\n';
    for (int k  = 1; k <= b[n][m]; k++)
        fout << sol[k] << ' ';
}