Cod sursa(job #1184323)

Utilizator SCBbestofSocaciu-Cumpanasu Bogdan SCBbestof Data 12 mai 2014 11:02:57
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>

#define MAXN 1025

using namespace std;

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

inline int maxim(int a , int b)
{
    return ((a > b) ? a : b);
}

int main()
{
    int N,M,aux, best, i,j;
    int A[MAXN][MAXN];

    f>>N>>M;

    vector<int> X;
    vector<int> Y;
    vector<int> sir;

    for(i = 0; i < M ; i++)
    {
        f>>aux;
        X.push_back(aux);
    }
    for(i = 0; i < N ; i++)
    {
        f>>aux;
        Y.push_back(aux);
    }

    for(i = 1 ; i <= M; i++)
        for(j = 1; j <= N; j++)
        {
            if (X[i] == Y[j])
                A[i][j] = A[i-1][j-1] + 1;
            else
                A[i][j] = maxim(A[i][j-1], A[i-1][j]);
        }

    for(i = M, j = N; i; )
        if (X[i] == Y[j])
        {
            sir.push_back(X[i]);
            --i;
            --j;
            ++best;
        }
        else if (A[i-1][j] < A[i][j-1])
            --j;
        else
            --i;

    g<<best<<endl;
    for(i = sir.size(); i ; i--)
    {
        g<<sir[i]<<" ";
    }
    return 0;
}