Cod sursa(job #3364362)

Utilizator proflaurianPanaete Adrian proflaurian Data 2 septembrie 2026 10:53:14
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
const int N=1030;
int n,m,k,i,j,a[N],b[N],c[N],L[N][N];
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>a[i];
    for(i=1;i<=m;i++)
        f>>b[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i]==b[j])
                L[i][j]=L[i-1][j-1]+1;
            else
                L[i][j]=max(L[i-1][j],L[i][j-1]);
    /// pentru lungime avem rezultatul
    i=n;
    j=m;
    k=L[n][m];
    g<<k<<'\n';
    while(k>0)
    {
        if(a[i]==b[j])
        {
            c[k]=a[i];
            i--;j--;k--;
        }
        else if(L[i-1][j]>L[i][j-1])i--;
        else j--;
    }
    /// acum reincarc k=Lmax
    k=L[n][m];
    for(i=1;i<=k;i++)
        g<<c[i]<<' ';
    g<<'\n';
    return 0;
}

/// SOLUTIE : Metoda programarii dinamice ( explicatie la final )
/// se considera prefixele formate din primele i elemente din a si primele j din b
/// vrem sa stim care ar fi lungimea maxima a unui subsir comun in acest caz
/// deci
    /// L[i][j] = lungimea maxima a unui subsir comun daca
    /// din primul sir alegem doar primele i elemente
    /// din al doilea sir alegem doar primele j elemente
/// Observatie : solutia intregii probleme va fi L[n][m]
/// Calcului lui L[i][j]
    /// daca a[i]=b[j] atunci L[i][j]=L[i-1][j-1]+1
    /// altfel L[i][j]=max(L[i-1][j],L[i][j-1])
    /// AM O FORMULA CARE IMI GASESTE L[i][j] folosind rezultate cu "i si j mai mici"