Cod sursa(job #880445)

Utilizator dica69Alexandru Lincan dica69 Data 16 februarie 2013 19:34:07
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>

using namespace std;
FILE *f1,*f2;
int x[1025],y[1025],a[1025][1025],n,m,i,j,sir[300],bst;

int max(int x,int y)
{if (x<y) return y;
else return x;}

void afis(int i,int j)
{while (x[i]!=y[j])
if (a[i-1][j]>a[i][j-1]) i--;
else j--;
if (a[i-1][j-1]>0) afis(i-1,j-1);
fprintf(f2,"%d ",x[i]);
}

int main()
{f1 = fopen("cmlsc.in","r");
f2 = fopen("cmlsc.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=n;i++) fscanf(f1,"%d",&x[i]);
for (i=1;i<=m;i++) fscanf(f1,"%d",&y[i]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (x[i]==y[j]) a[i][j]=a[i-1][j-1]+1;
else a[i][j]=max(a[i-1][j],a[i][j-1]);
fprintf(f2,"%d\n",a[n][m]);
afis(n,m);
fprintf(f2,"\n");
fclose(f2);fclose(f1);
    return 0;
}