Cod sursa(job #2313401)

Utilizator LascoDaniilDanielDFS LascoDaniil Data 6 ianuarie 2019 20:23:05
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define  max(a,b)(( a>b) ? a : b)
using namespace std;
ifstream fin  ("cmlsc.in");
ofstream fout ("cmlsc.out");

int D[1024][1024];
int n,m;

int main()
{
    int a[1024];
    int b[1024];
    fin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        fin >> a[i];
    for(int j = 1 ; j <=m ;j++)
        fin >> b[j];

    for(int i = 1; i <=n ; i++){
        for(int 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]);
            }
        }
    }

    // solution create
    int i,j,c=0,arr[1024],k=0;
    i= n; j =m;
    while( i>1 &&  j>1){
        if(a[i] == b[j]){
            arr[k] = a[i];
            fout << arr[k] << " ";
            --i;
            --j;
            c++;
            k++;
        }else if(D[i-1][j] < D[i][j-1]){
            --j;
        }
        else{
            --i;
        }
    }

    fout << c << "\n";
    return 0;
}