Cod sursa(job #1795941)

Utilizator PogonetPogonet Artiom Pogonet Data 2 noiembrie 2016 22:46:12
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
using namespace std;
ifstream f ("cmlsc.in");
ofstream g ("cmlsc.out");
int n , m , a[1025] , b[1025] , x[1025][1025] , sol[1025] , k;
void citire ()
{
    f >> n >> m;
    for (int i = 1; i <= n; ++i)
        f >> a[i];
    for (int j = 1; j <= m; ++j)
        f >> b[j];
}
void rezolvare ()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i] == b[i])
                x[i][j] = 1 + x[i-1][j-1];
            else
                x[i][j] = max(x[i][j-1] , x[i-1][j]);
        }
    }
}
void rezolvare2()
{   g << x[n][m];
    int i = n , j = m;
    if (a[i] == b[j])
    {
        sol[++k] = a[i];
        i--; j--;
    }
    else
    {
        if (x[i-1][j] > x[i][j-1]) i--;
        else i--;
    }
    for (; k > 0; --k) g << sol[k] << ' ';
}
int main ()
{
    citire();
    rezolvare();
    rezolvare2();
    g.close ();
    return 0;
}