Cod sursa(job #1342122)

Utilizator ducu97Radu Seteanu ducu97 Data 13 februarie 2015 15:50:33
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <algorithm>
#define NMax 1025

using namespace std;

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

int T[NMax][NMax], v1[NMax], v2[NMax];

int main()
{
    int n,m,i,j,k=1;

    in>>n>>m;

    for(i = 1; i <= n; ++ i)
        in >> v1[i];
    for(j = 1; j <= m; ++ j)
        in >> v2[j];

    for(i = 1; i <= n; ++ i)
    {
        for(j = 1; j <= m; ++ j)
        {
            if(v1[i]!=v2[j])
                T[i][j] = max(T[i-1][j], T[i][j-1]);
            else
                T[i][j] = max(1+T[i-1][j-1], max(T[i-1][j], T[i][j-1]));
        }
    }
    out << T[n][m] << endl;

    for(i = 1; i <= n; ++ i)
    {
        for(j = 1; j <= m; ++j)
        {
            if(T[i][j-1]<T[i][j] && k == T[i][j])
            {
                out<<v1[i]<<" ";
                k++;
            }
        }
    }

    return 0;
}