Cod sursa(job #1376974)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 5 martie 2015 19:34:49
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
using namespace std;
int i, j, n, m, a[1025], b[1025], t[1025][1025], sol[1025], lg;
inline int max(int a, int b){if (a>=b) return a; else return b;}
int main(){
    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=n;i++) {scanf("%d", &a[i]); t[i][0]=0;}
    for (i=1;i<=m;i++) scanf("%d", &b[i]);
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) {
        if (a[i]==b[j]) t[i][j]=t[i-1][j-1]+1;
            else t[i][j]=max(t[i-1][j], t[i][j-1]);
    }
    printf("%d\n", t[n][m]);
    i=n; j=m; lg=0;
    while (i>0) {
        if (a[i]==b[j]) {sol[++lg]=a[i]; i--; j--;}
        if (t[i-1][j]<t[i][j-1]) j--; else i--;
    }
    for (i=lg;i>=1;i--) printf("%d ", sol[i]);
    printf("\n");
    return 0;
}