Cod sursa(job #1847190)

Utilizator flvflvFlavius Ilinoiu flvflv Data 14 ianuarie 2017 13:16:25
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#define MAX 1025

using namespace std;

ifstream f("cmlsc.in");
ofstream g("cmlsc.out");

int n,m;
int a[MAX],b[MAX],c[MAX];
int v[MAX][MAX];

void solutie(int n, int m)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i] == b[j]) v[i][j] = 1 + v[i-1][j-1];
            else
                v[i][j] = max(v[i-1][j],v[i][j-1]);
        }
    }
    g<<v[n][m]<<"\n";

    int i=n;
    int j=m;

    int sol[MAX];
    int index = 0;

    while(i!=0 && j!=0)
    {
        if(a[i] == b[j])
        {
            sol[++index] = a[i];
            i--;
            j--;
        }
        else
            if(a[i-1]>b[j-1]) i --;
            else j--;
    }

    for(int i = index;i>=1;i--)  g<<sol[i]<<" ";
    g<<endl;
}

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

    solutie(n,m);
    g.close();

    return 0;
}