Cod sursa(job #1841009)

Utilizator crazylamaRiclea Andrei crazylama Data 5 ianuarie 2017 07:10:06
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <cmath>
using namespace std;

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

void solve(int n, int m, int** mat, int *v1, int *v2)
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (v1[i - 1] == v2[j - 1])
                mat[i][j] = mat[i - 1][j - 1] + 1;
            else
                mat[i][j] = max(mat[i - 1][j], mat[i][j - 1]);
}

void lexicografic_cmlsc(int n, int m, int** mat, int* v1, int* v2, int* sol)
{
    int lg = mat[n][m];
    for (int i1 = n; i1 > 0 && lg > 0; --i1)
        for (int j1 = m; j1 > 0 && lg > 0; --j1)
        if (mat[i1][j1] == lg && v1[i1 - 1] == v2[j1 - 1])
        {
            int mini = 257;
            int imin = i1, jmin = j1;
            for (int i2 = i1; i2 >= 0; --i2)
                for (int j2 = j1; j2 >= 0; --j2)
                if (mat[i2][j2] == lg && v1[i2 - 1] == v2[j2 - 1] && mini > v1[i2 - 1])
                {
                    mini = v1[i2 - 1];
                    imin = i2;
                    jmin = j2;
                }
            sol[--lg] = mini;
            i1 = imin;
            j1 = jmin;
        }
}

void one_cmlsc(int n, int m, int** mat, int* v1, int *v2, int* sol)
{
    int lg = mat[n][m];
    for (int i = n; i > 0 && lg > 0; --i)
        for (int j = m; j > 0 && lg > 0; --j)
            if (mat[i][j] == lg && v1[i - 1] == v2[j - 1])
            {
                sol[--lg] = v1[i - 1];
                --j;
                --i;
            }
}

int main()
{
    int n, m;
    f >> n >> m;
    int **mat = new int*[n + 1];
    int *v1 = new int[n]();
    int *v2 = new int[m]();
    int *sol = new int[max(n, m)]();
    for (int i = 0; i <= n; ++i)
        mat[i] = new int[m + 1]();
    for (int i = 0; i < n; ++i)
        f >> v1[i];
    for (int i = 0; i < m; ++i)
        f >> v2[i];
    solve(n, m, mat, v1, v2);
    //lexicografic_cmlsc(n, m, mat, v1, v2, sol);
    one_cmlsc(n, m, mat, v1, v2, sol);
    g << mat[n][m] << "\n";
    for (int i = 0; i < mat[n][m]; ++i)
        g << sol[i] << " ";
    return 0;
}