Cod sursa(job #308574)

Utilizator razvan_emPrecupas Razvan razvan_em Data 27 aprilie 2009 20:33:50
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
using namespace std;
#define maxim(a, b) ((a > b) ? a : b)  
ofstream ofis("cmlsc.out");
ifstream ifis("cmlsc.in");
long n,m,a[1909],b[1523],i,j,d[1434][1930],sir[1234],lmax;
//long maxim(long, long);

int main()
{
    ifis>>n>>m;
    for (i=1; i<=n; i++)
    ifis>>a[i];
    for (i=1; i<=m; i++)
    ifis>>b[i];
    
    for (i=1; i<=m; i++)
    for (j=1; j<=n; j++)
    if (a[i]==b[j]) d[i][j]=1+d[i-1][j-1];
    else d[i][j]=maxim(d[i-1][j],d[i][j-1]);
    
    for (i=m, j=n; i; )
    if (a[i]==b[j]) {sir[++lmax]=a[i]; --i; --j;}
    else if (d[i-1][j]<d[i][j-1]) --j;
    else --i;
    
    ofis<<lmax<<"\n";
    for (i=lmax; i>=1; --i)
    ofis<<sir[i]<<" ";
    return 0;
}

//long maxim(long x, long y)
//{
//     if (x<=y) return y;
//     return x;
//}
//