Cod sursa(job #1651689)

Utilizator Sergiu1256Ionita Sergiu1256 Data 13 martie 2016 18:41:47
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int rs[1025],r,A[1025],B[1025],M,N,D[1025][1025];
int main(){
	int j,i;
    fin >> N >> M;
    for(i = 1;i<=N;i++){
        fin >> A[i];
    }
    for(i = 1;i<=M;i++){
        fin >> B[i];
    }
     
    for(i = 1;i<=N;i++)
        for(j = 1;j<=M;j++){
            if(A[i] == B[j]) D[i][j] = D[i-1][j-1] + 1;else
            D[i][j] = max(D[i-1][j],D[i][j-1]);
        }
    fout << D[N][M]<<'\n';
     
    for(i = N,j = M;i; ){
        if(A[i] == B[j]){
            rs[++r] = A[i];
            i--;
            j--;
        }else
        if(D[i-1][j] < D[i][j-1]) j--; else i--;
    }
     
    for(i = r;i>0;i--) fout << rs[i] <<' ';
    return 0;
}