Cod sursa(job #2267887)
Utilizator | Noroc Andrei Mihail andreiutu111 | Data | 24 octombrie 2018 10:12:22 |
---|---|---|---|
Problema | Cel mai lung subsir comun | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include<fstream>
using namespace std;
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int M,N,A[1024],B[1024],D[1024][1024],k,nr[1024];
int main()
{
f>>M>>N;
for(int i=1;i<=M;++i)f>>A[i];
for(int i=1;i<=N;++i)f>>B[i];
for(int i=1;i<=M;++i)
for(int j=1;j<=N;++j)
if(A[i]==B[j])D[i][j]=1+D[i-1][j-1];
else D[i][j]=max(D[i-1][j],D[i][j-1]);
for(int i=M,j=N;i>0;)
if(A[i]==B[j])nr[++k]=A[i],--i;
else if(D[i][j-1]>D[i-1][j])--j;
else --i;
g<<k<<'\n';
for(int i=k;i>0;--i)g<<nr[i]<<' ';
return 0;
}