Cod sursa(job #1658441)

Utilizator hegedusPaul Hegedus hegedus Data 21 martie 2016 15:19:15
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <cstdio>
using namespace std;

const int nmax=1025;

short a[nmax][nmax],v1[nmax],v2[nmax],v[nmax],n1,n2,x,y,x1,y1,x2,y2,k,kmax;

void citire()
{
    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);
    scanf("%d%d",&n1,&n2);
    for(x=1;x<=n1;x++)
        scanf("%d",&v1[x]);
    for(y=1;y<=n2;y++)
        scanf("%d",&v2[y]);
}

int maxim(int i, int j)
{
    if (i>j) return i;
    else return j;
}

int main()
{
    citire();

    for(x=1;x<=n1;x++)
        for(y=1;y<=n2;y++)
        {
            if(v1[x]==v2[y])
            {
                a[x][y]=a[x-1][y-1]+1;
                if (a[x][y]>kmax) {kmax=a[x][y]; x2=x; y2=y;}
            }
            else a[x][y]=maxim(a[x-1][y],a[x][y-1]);
        }
    printf("%d\n",kmax);
    k=kmax;
    do
    {
        v[k--]=v1[x2];
        if (k)
        {
            for(x1=x2-1;x1>=1;x1--)
            {
                for(y1=y2-1;y1>=1;y1--)
                    if (a[x1][y1]==k) break;
                if (a[x1][y1]==k) break;
            }
            x2=x1; y2=y1;
        }
    }while(k);

    for(x=1;x<=kmax;x++) printf("%d ",v[x]);
    printf("\n");
    return 0;
}