Cod sursa(job #2368965)

Utilizator stefyo1Vida Laura Stefana stefyo1 Data 5 martie 2019 20:09:46
Problema Cel mai lung subsir comun Scor 80
Compilator cpp-64 Status done
Runda pregatire_cls10_oji Marime 0.93 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int n,m,x[1025],y[1025],lcs[1001][1001];
void rezolvare()
{
    int k,h;
    for(k=1;k<=n;k++)
        for(h=1;h<=m;h++)
        if(x[k]==y[h])
           lcs[k][h]=lcs[k-1][h-1]+1;
        else
            lcs[k][h]=max(lcs[k][h-1],lcs[k-1][h]);
}
void afisare_sol_max(int k,int h)
{
    if(lcs[k][h])
        if(x[k]==y[h])
        {
              afisare_sol_max(k-1,h-1);
              g<<x[k]<<" ";
        }
    else
    {
        if(lcs[k][h]==lcs[k-1][h])
            afisare_sol_max(k-1,h);
        else
            if(lcs[k][h]==lcs[k][h-1])
            afisare_sol_max(k,h-1);
    }
}
int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>x[i];
    for(i=1;i<=m;i++)
        f>>y[i];
    rezolvare();
    g<<lcs[n][m]<<"\n";
    afisare_sol_max(n,m);
    return 0;
}