Cod sursa(job #1099062)

Utilizator c0rn1Goran Cornel c0rn1 Data 5 februarie 2014 15:25:46
Problema Cel mai lung subsir comun Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;

FILE *f1=freopen("cmlsc.in", "r", stdin);
FILE *f2=freopen("cmlsc.out", "w", stdout);
int n, m, a[1025], b[1025], l[1025][1025], dr[1025];
const int di[3]={-1, -1, 0}, dj[3]={0, -1, -1};

void cit()
{
    scanf("%d%d", &n, &m);
    for (int i=0; i<n; i++)
        scanf("%d", &a[i]);
    for (int j=0; j<m; j++)
        scanf("%d", &b[j]);
}

int lmax()
{
    for (int j=0; j<n; j++)
        if (a[j]==b[j])
            l[0][j]=1;
    for (int i=0; i<m; i++)
        if (a[i]==b[i])
            l[i][0]=1;
    for (int i=1; i<n; i++)
        for (int j=1; j<m; j++)
        {
            int maxi=0;
            for (int v=0; v<3; v++)
                maxi=max(maxi, l[i+di[v]][j+dj[v]]);
            l[i][j]=maxi;
            if (maxi==l[i-1][j-1] && a[i]==b[j])
                l[i][j]++;
        }
    return l[n-1][m-1];
}

void drum()
{
    int i=n-1, j=m-1;
    while (i!=0 || j!=0)
    {
        if (a[i]==b[j])
        {
            dr[++dr[0]]=a[i];
            if (i>0)
                i--;
            if (j>0)
                j--;
        }
        else if (l[i-1][j-1]>=l[i-1][j] && l[i-1][j-1]>=l[i][j-1])
        {
            if (i>0)
                i--;
            if (j>0)
                j--;
        }
        else if (l[i-1][j]>=l[i-1][j-1] && l[i-1][j]>=l[i][j-1] && j-1>=0)
            i--;
        else if (i-1>=0)
            j--;
    }
    if (a[i]==b[j])
        dr[++dr[0]]=a[i];
    for (int i=dr[0]; i>=1; i--)
        printf("%d ", dr[i]);
}

void sol()
{
    printf("%d\n", lmax());
    drum();
}

int main()
{
    cit();
    sol();
    return 0;
}