Cod sursa(job #2151410)

Utilizator stefanbrb10Barbu Stefan stefanbrb10 Data 4 martie 2018 14:07:23
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
using namespace std;
ifstream input("cmlsc.in");
ofstream print("cmlsc.out");
int DP[1025][1025],LCS[1025];
int A[1025],B[1025];
int i,j,n,m,lg;

void Read(){
    input>>m>>n;
    for(i=1;i<=m;i++)input>>A[i];
    for(i=1;i<=n;i++)input>>B[i];
}

void Rezolvare(){
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++){
           if(A[i]==B[j])
                DP[i][j]=DP[i-1][j-1]+1;
           else
                DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
    }
    print<<DP[m][n]<<'\n';
    lg=DP[m][n];
    for(i=m;i>=1;i--)
    for(j=n;j>=1;j--)
            if(DP[i][j]==lg && A[i]==B[j])
                    LCS[lg--]=A[i];
    for(i=1;i<=DP[m][n];i++)print<<LCS[i]<<" ";
}

int main(){
    Read();
    Rezolvare();
    return 0;
}