Cod sursa(job #371202)

Utilizator pregatireCont de pregatire pregatire Data 4 decembrie 2009 10:22:15
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <stdio.h>

int M, N, sol[1024], bst;
int A[1024], B[1024], opt[2][1024], tai[2][1024];

void solve(int l1, int r1, int l2, int r2)
{
    if (l1 > r1 || l2 > r2)
        return ;
    
    int i, j;
    if (l1 == r1 || l2 == r2)
    {
        for (i = l1; i <= r1; ++i)
            for (j = l2; j <= r2; ++j)
                if (A[i] == B[j])
                {
                    sol[i] = 1;
                    ++bst;
                    return ;
                }
        return ;
    }
    
    int m = (l1 + r1) / 2;
    int crt = 0, prev = 1;
    
    for (i = l1; i <= r1; ++i)
        opt[crt][i] = 0;
    for (i = l1; i <= r1; ++i)
    {
        crt ^= 1; prev ^= 1;
        for (j = l2; j <= r2; ++j)
            if (A[i] == B[j])
            {
                opt[crt][j] = opt[prev][j-1] + 1;
                tai[crt][j] = tai[prev][j-1];
                if (i <= m)
                    tai[crt][j] = j;
            }
            else if (opt[crt][j-1] < opt[prev][j])
            {              
                opt[crt][j] = opt[prev][j];
                tai[crt][j] = tai[prev][j];
            }
            else
            {
                opt[crt][j] = opt[crt][j-1];
                tai[crt][j] = tai[crt][j-1];
            }
    }
    
    solve(l1, m, l2, tai[crt][r2]);
    solve(m+1, r1, tai[crt][r2]+1, r2);
}

int main()
{
    int i, j;
    
    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 (j = 1; j <= N; ++j)
        scanf("%d", &B[j]);
    
    solve(1, M, 1, N);    
    
    printf("%d\n", bst);
    for (i = 1; i <= M; ++i)
        if (sol[i])
            printf("%d ", A[i]);
    printf("\n");
        
    return 0;
}