Cod sursa(job #811422)

Utilizator cristian.ion94Ion Cristian cristian.ion94 Data 12 noiembrie 2012 10:36:20
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#define DMAX 1025

using namespace std;

int n, m;
int a[DMAX],b[DMAX];
int LCS[DMAX][DMAX];
int OP[DMAX][DMAX];

void Citire();
void pd();
void afisare();

int main()
{
    Citire();
    pd();
    afisare();
    return 0;
}

void Citire()
{
    ifstream fin("cmlsc.in");

    fin >> n >> m;

    int i,j;
    for(i = 0; i < n; i++)
        fin >> a[i];
    for(j = 0; j < m; j++)
        fin >> b[j];

    fin.close();
}

void pd()
{
    int i, j;
    for(i = 0; i < n; i++)
        LCS[i][m] = 0;
    for(j = 0; j < m; j++)
        LCS[n][j] = 0;

    for(i = n-1; i >= 0; i--)
    {
        for(j = m-1; j >= 0; j--)
        {
            if(a[i] == b[j])
            {
                LCS[i][j] = 1 + LCS[i+1][j+1];
                OP[i][j] = 1;
            }
            else
            {
                if(LCS[i+1][j] > LCS[i][j+1])
                {
                    LCS[i][j] = LCS[i+1][j];
                    OP[i][j] = 2;
                }
                else
                {
                    LCS[i][j] = LCS[i][j+1];
                    OP[i][j] = 3;
                }
            }
        }
    }
}

void afisare()
{
    ofstream fout("cmlsc.out");
    fout << LCS[0][0] << '\n';

    int i=0,j=0;
    while(i < n && j < m)
    {
        if(OP[i][j] == 1)
        {
            fout << a[i] << ' ';
            i++;
            j++;
        }
        if(OP[i][j] == 2)
        {
            i++;
        }
        if(OP[i][j] == 3)
        {
            j++;
        }
    }

    fout.close();
}