Cod sursa(job #2369363)

Utilizator Andreea62389Andreea Tebrean Andreea62389 Data 5 martie 2019 22:42:54
Problema Cel mai lung subsir comun Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int v[1025], w[1025], mat[1025][1025];
int main()
{
    int n, m, i, j, nr=0;
    fin >> n >> m;
    for(i=1; i<=n; i++)
        fin >> v[i];
    for(j=1; j<=m; j++)
        fin >> w[j];
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            if(v[i]==w[j])
                mat[i][j]=mat[i-1][j-1]+1;
            else
                mat[i][j]=max(mat[i-1][j], mat[i][j-1]);
        }
    i=n; j=m;
    while(i && j)
    {
        if(mat[i][j]==mat[i-1][j-1]+1)
        {
            nr++;
            w[nr]=v[i];
            i--;
            j--;
        }
        else
            if(max(mat[i-1][j], mat[i][j-1])==mat[i-1][j])   i--;
        else   j--;
    }
    fout << mat[n][m] << "\n";
    while(nr)
    {
        fout << w[nr] << " ";
        nr--;
    }
    return 0;
}