Cod sursa(job #1330095)

Utilizator forever16Alex M forever16 Data 30 ianuarie 2015 13:09:35
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include<fstream>
#define maxim 1024
using namespace std;
    ifstream f("cmlsc.in");
    ofstream g("cmlsc.out");

int main()
{   int n,m, a[maxim], b[maxim],sir[maxim],bst=0, d[maxim][maxim]={0};
 f>>m>>n;
for(int i=1; i<=m; i++) f>>a[i];
for(int j=1; j<=n; j++) f>>b[j];

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

    for (int i=m, j=n; i;)
        if (a[i] == b[j])
            sir[++bst] = a[i], --i, --j;
        else if (d[i-1][j] < d[i][j-1])
            --j;
        else
            --i;
for(int i=bst; i; i--) g<<sir[i]<<" ";
        return 0; }