UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Entrega: 27 de febrero de 2006 a las 10pm
Diseñe 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. Suponga 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 alguna
forma mejor que esta? Escriba un programa basado en su 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. Puede suponer que 1 <= M <= N <= 1000.
¿Cuál es
el valor de N más
grande que puede resolver en un minuto? ¿Y en una hora?