Cod sursa(job #498963)

Utilizator nbibestNeagu Bogdan Ioan nbibest Data 7 noiembrie 2010 20:31:50
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
using namespace std;

int m,n,i,j,a[1025],b[1025],d[1025][1025],v[1025];

int main()
{

    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);

    scanf("%d %d",&m,&n);

    for (i=1;i<=m;i++) scanf("%d",&a[i]);
    for (i=1;i<=n;i++) scanf("%d",&b[i]);

    for (i=1;i<=m;i++)
    for (j=1;j<=n;j++)
    {
        if (a[i]==b[j])
        {
        d[i][j]=d[i-1][j-1]+1;
            if (v[d[i][j]]==0 ) v[d[i][j]]=a[i];
        }
        else
            if (d[i-1][j]>d[i][j-1])
            d[i][j]=d[i-1][j];
            else
            d[i][j]=d[i][j-1];

    }

    printf("%d\n",d[m][n]);


    for (i=1;i<=d[m][n];i++)
    printf("%d ",v[i]);

    return 0;
}