Cod sursa(job #1350558)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 20 februarie 2015 20:39:19
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>

#include <stack>

#define MAX(a,b) ((a)>(b)?(a):(b))

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

    int i, j, n, m;
    int mat[1024][1024];
    int v1[1024], v2[1024];

int main()
{

    stack<int> sol;
    int solLength = 0;


    f>>n>>m; // n - linii, m -  coloane

    for(i = 1; i <= n; ++i)
    {
        f>>v1[i];
    }

    for(j = 1; j <= m; ++j)
    {
        f>>v2[j];
    }

    /* the magic happens here */
    for(i = 1; i <= n; ++i)
    {
        for(j = 1; j <= m; ++j)
        {
            if(v1[i] != v2[j])
            {
                mat[i][j] = MAX(mat[i - 1][j], mat[i][j - 1]);
            } else {
                mat[i][j] = mat[i - 1][j - 1] + 1;
            }

        }
    }


    solLength = mat[n][m];

    i = n;
    j = m;

    while(i != 0 && j != 0) {
        if(mat[i - 1][j - 1] == mat[i][j] - 1) {
            sol.push(v1[i]); // or v2[j]
            i = i - 1;
            j = j - 1;
        } else {
            if(mat[i][j] == mat[i - 1][j] ) {
                --i;
            } else {
                --j;
            }
        }
    }

    g<<solLength<<"\n";
    while(!sol.empty())
    {
        g<<sol.top()<<" ";
        sol.pop();
    }

    return 0;
}