Problema 1: Diseña un algoritmo usando la técnica de programación dinámica para resolver el siguiente problema: Sea N un entero positivo y sean A y B dos arreglos A[1], A[2], ..., A[N] y B[1], B[2], ..., B[N] de enteros positivos. Los índices 1 <= I1 < I2 < ... < IK <= N y 1 <= J1 < J2 < ... < JK <= N forman un subarreglo ascendente común de A y B de longitud K si se cumple que A[I1] = B[J1] < A[I2] = B[J2] < ... < A[IK] = B[JK]. Su algoritmo deberá encontrar un subarreglo ascendente común de A y B con la mayor longitud posible. Por ejemplo, si N = 9, A = [3, 1, 4, 1, 5, 9, 2, 6, 5] y B = [9, 2, 1, 3, 4, 6, 5, 7, 6] entonces los índices I1 = 1, I2 = 3, I3 = 5 e I4 = 8 y J1 = 4, J2 = 5, J3 = 7 e I4 = 9 forman el subarreglo ascendente [3, 4, 5, 6] de longitud 4. Escribe un programa llamado sascomZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) basado en tu algoritmo que acepte como entrada el entero positivo N y dos arreglos A y B de N enteros positivos y que escriba como salida la máxima longitud K de un subarreglo ascendente común de A y B. Puedes suponer que 1 <= N <= 1000 y que A y B son arreglos de int.
| Ejemplo de entrada |
Ejemplo de salida |
| 9 3 1 4 1 5 9 2 6 5 9 2 1 3 4 6 5 7 6 |
4 |
Problema 2: Diseña un algoritmo usando programación dinámica para resolver el siguiente problema: Un cierto lenguaje de programación le permite al programador cortar una cadena en dos partes. Debido a que esta operación involucra copiar la cadena original, cuesta N unidades de tiempo cortar una cadena de N caracteres en dos partes. Supón que un programador quiere cortar una cadena en varias partes. El orden en el que se hagan los cortes puede afectar la cantidad total de tiempo empleada. Por ejemplo, suponga que se quiere cortar una cadena de 20 caracteres justo después de los caracteres 3, 8 y 10 (numerando los caracteres en orden ascendente, de izquierda a derecha y comenzando con el 1). Si los cortes se hicieran de izquierda a derecha, entonces el primer corte costaría 20 unidades de tiempo, el segundo costaría 17 unidades de tiempo y el tercero costaría 12 unidades de tiempo, para un total de 49 unidades de tiempo. Si los cortes se hicieran de derecha a izquierda, entonces el primer corte costaría 20 unidades de tiempo, el segundo costaría 10 unidades de tiempo y el tercero costaría 8 unidades de tiempo, para un total de 38 unidades de tiempo. Hay una forma mejor que esta que tarda 37 unidades de tiempo. Escribe un programa llamado cortacZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) basado en tu algoritmo que acepte como entrada un entero positivo N (la longitud de la cadena) seguido de otro número positivo M (el número de cortes a realizar) y seguido de M números positivos X1, ..., XM (los distintos lugares donde se desea realizar los cortes, ordenados de izquierda a derecha) y que escriba como salida el tiempo mínimo T que necesita el programador para cortar la cadena en esos lugares. Puedes suponer que 1 <= M <= N <= 1000.
| Ejemplo de entrada |
Ejemplo de salida |
| 20 3 3 8 10 |
37 |
Notas: Tus programas no deben leer ni escribir nada adicional a lo que se indica en el enunciado. El tiempo de ejecución de sus algoritmos será considerado como parte de la evaluación.