Cod sursa(job #2456726)

Utilizator gabriel_212MitracheG gabriel_212 Data 15 septembrie 2019 12:53:48
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;

int main()
{ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
   int N,M,index=0;
   int A[1024]{},B[1024]{},C[1024][1024]{},sol[1024]{};
   fin>>M>>N;
   for(int i=1;i<=M;i++){
    fin>>A[i];
   }
    for(int i=1;i<=N;i++){
    fin>>B[i];
   }
   for(int i=1;i<=M;i++){
    for(int j=1;j<=N;j++){
        if(A[i]==B[j]){
            C[i][j]=C[i-1][j-1]+1;
        }else C[i][j]=max(C[i-1][j],C[i][j-1]);
    }
   }
   int i=M,j=N;
   while(i>0&&j>0){
if(A[i]==B[j]){
    sol[++index]=A[i];
    --i;
    --j;
}else if(C[i-1][j]<C[i][j-1]){
--j;
}else --i;
   }
   fout<<index<<"/n";
   for(i=index;i;--i){
    fout<<sol[i];
   }
   fin.close();
   fout.close();
    return 0;
}