Cod sursa(job #1738550)

Utilizator daymon_cDumitru Chitoraga daymon_c Data 6 august 2016 23:05:16
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>

int n, m, a[1025], b[1025], v[1025][1025], sir[1025], bst;
int maxim(int a, int b) { return (a>b)? a : b; }

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

    scanf("%d %d", &m, &n);
    for(int i=1; i<=n; ++i)
        scanf("%d", &b[i]);
    for(int i=1; i<=m; ++i)
        scanf("%d", &a[i]);
    
    for(int i=1; i<=m; ++i)
        for(int j=1; j<=n; ++j)
            if(a[i]==b[j])
                v[i][j] = v[i-1][j-1] + 1;
            else
                v[i][j] = maxim(v[i-1][j], v[i][j-1]);
    

    for(int i=m, j=n; i;)
        {
            if(a[i]==b[j]) { sir[bst++] = a[i]; i--; j--; }
            else if(v[i-1][j]<v[i][j-1]) j--;
            else i--;
        }
        printf("%d\n", bst);
    for(int i=bst - 1; i>=0; --i) printf("%d ", sir[i]);

    return 0;
}