Combinando Plastilinas
Hay bolas de plastilina de varios tamaños en una fila. Usted desea formar la mayor bola de plastilina posible desarrollando las siguientes operaciones:
• Si dos bolas adyacentes tienen el mismo tamaño, entonces puede combinarlas y hacer una nueva bola. El tamaño de la nueva bola es la suma de los tamaños de las dos bolas viejas. Esta ocupa la posición previamente ocupada por las dos bolas viejas.
• Si dos bolas tienen el mismo tamaño y hay exactamente una bola entre ellas, entonces puede combinar estas tres bolas para hacer una nueva bola de plastilina (la bola del medio no necesita ser del mismo tamaño que las otras dos). El tamaño de la nueva bola es la suma de los tamaños de las tres bolas viejas. Esta ocupa la posición previamente ocupada por las tres bolas viejas.
Usted puede desarrollar cada operación las veces que desee. Determine el tamaño de la mayor bola de plastilina después de desarrolladas 0 o más operaciones.
Entrada
La primera línea contiene el entero, . La próxima línea contiene enteros separados por espacio representando los tamaños de las bolas de plastilina desde izquierda a derecha. Cada entero es al menos y a lo sumo .
Salida
Imprima el tamaño de la mayor bola de plastilina que usted puede formar.
Ejemplo #1 de Entrada
7
47 12 12 3 9 9 3
Ejemplo #1 de Salida
48
Ejemplo #2 de Entrada
4
1 2 3 1
Ejemplo #2 de Salida
3
Explicación del ejemplo 1: Un posible conjunto de movimientos para crear una bola de tamaño es combinar y para formar una bola de tamaño ,entonces combinar y para formar una de tamaño , luego se combinan , y y se forma una de tamaño . Finalmente combinamos las dos bolas de tamaño y formamos la de tamaño .
Explicación del ejemplo 2: No hay posibles movimientos así que la de mayor tamaño es .
Comments
Así mismo es. De verdad que el usuario aniervs da unas explicaciones geniales, muchas gracias por querer compartir tus conocimientos y ayudarnos a aprender más.?
Con el paso del tiempo me he dado cuenta que el 99% de los comentarios que hace el usuaio : //aniervs// sobre la solucion de un problema deberian ser añadidos como editorial para el problema.
alguien podria decirme q tipo de DP podria aplicar en este problema
Una plastilina representa a un subrango contiguo del arreglo original, y su valor es igual a la suma de dicho subrango. Entonces, la respuesta es la suma de un rango contiguo del arreglo original.
Solo necesitamos saber cuáles son los rangos que pueden resultar en una sola plastilina (llamémoslos buenos). Eso lo podemos saber con programación dinámica.
Digamos que nos dice si el rango es . Obviamente, los rangos de tamaño son buenos, es decir, para todo . Veamos cómo saberlo para rangos de longitud mayor que .
Para poder obtener el rango como una sola plastilina podíamos:
Haber hecho la primera operación con el rango y el rango para algún . Podemos elegir un si el rango es bueno, el rango es bueno, y además la suma del rango es igual a la suma del rango .
Haber hecho la segunda operación con el rango , el rango y el rango para algún par . El rango representa la plastilina intermedia, y los rangos y serían las plastilinas de igual tamaño. Podemos elegir un rango si , y son los tres buenos, y además la suma del rango es igual a la suma del rango .
El operador denota el or-inclusivo (
||
en C++), y el operador denota el and (&&
en C++).Código de ejemplo:
Ahora, esa solución tiene complejidad temporal ; hay que optimizarla. La parte que necesitamos cambiar es cómo iteramos por los pares .
Supongamos que están fijos, a medida que aumentamos , la suma del rango aumenta (ya que los elementos del arreglo son positivos). Y a medida que aumentamos , la suma del rango disminuye. Como queremos que , si aumentamos , entonces no puede aumentar. Podemos, en lugar de iterar por todos los pares , llevar dos punteros: inicia en , y inicia en . se mueve de en hacia la derecha, y cada vez que se mueva un paso, movemos a la izquierda mientras y .
Una vez que se movió todo lo requerido, y si , usamos la misma fórmula.
Como para fijos, solo se mueve hacia la derecha, y a la izquierda, cada posición del rango es visitada una vez por , y una vez por . Por tanto, para fijos, se hacen iteraciones. Eso quiere decir que la complejidad temporal ahora es .