Fotolog
2010-10-12: A través del espejo
2010-10-10: ¡La radio habla en binario!
2010-09-16: Gigaminx (regalo por mi cumple)
2010-09-05: Trini en bici
2010-08-28: Valporquero
2010-08-22: Mi bici nueva
2010-08-13: Boda de Mario y Ana
2010-08-07: De cañones en Guara
2010-08-05: Trini y Mari en Marbella
2010-08-03: Trini y Chelo en Tabarca
Volver a la lista de problemas
History Grading
111.c
#include <stdio.h>
#include <string.h>
int n;
int orig[25];
int dest[25];
int tab[25][25];
#define MAX(a,b) ((a) > (b) ? (a) : (b))
int
lcs(int a, int b) {
int i,j;
if (a==0 || b==0) {
return 0;
}
if (tab[a][b]) {
return tab[a][b];
}
if (orig[a] == dest[b]) {
tab[a][b]=1+lcs(a-1,b-1);
return tab[a][b];
}
i = lcs(a-1,b);
j = lcs(a,b-1);
tab[a][b] = MAX(i,j);
return tab[a][b];
}
int
main(void) {
int i;
int a;
scanf("%d", &n);
for (i=1; i<=n; i++) {
scanf("%d", &a);
orig[a] = i;
}
while (1) {
for (i=1; i<=n; i++) {
if (scanf("%d", &a) != 1) {
return 0;
}
dest[a] = i;
}
memset(tab, 0, sizeof(tab));
printf("%d\n", lcs(n, n));
}
}