El Escape Vacuno
El Granjero Juan ha olvidado reparar un hueco en el cerco de su granja y sus vacas
se han escapado y están armando desorden.En cada minuto que una vaca que esté fuera del cerco, causa un daño que cuesta un dólar. El Granjero Juan debe visitar cada vaca para ponerle un lazo de tal manera que la vaca se calme y pare el daño.
Afortunadamente, las vacas están ubicadas en posiciones distintas a lo largo de una recta en una carretera fuera de la granja. El Granjero Juan conoce la posición de cada vaca
relativa al portón (posición
) donde Granjero Juan comienza.
El Granjero Juan se desplaza una unidad de distancia por minuto y puede enlazar una vaca instantáneamente. Determine, por favor, el orden que Granjero Juan debe visitar las vacas de tal manera que él pueda minimizar el costo del daño; usted debería calcular el costo total del daño en este caso.
Entrada
Una línea con el número de vacas, . A continuación
líneas, donde cada una contiene un entero
.
Salida
Una línea conteniendo un solo entero, el costo total mínimo del daño.
Ejemplo de Entrada
4
-2
-12
3
7Ejemplo de Salida
50Explicación del ejemplo: Cuatro vacas ubicadas en las posiciones: -2, -12, 3 y 7. El orden óptimo de visita es –2, 3, 7, -12. El Granjero Juan llega a la posición –2 en 2 minutos para un total de 2 dólares para esa vaca. El gasta 4 minutos más para llegar a 7 a un costo de 7 + 4 = 11 dólares para esa vaca. Finalmente, él gasta 19 minutos para ir a –12 con un costo de 11 + 19 = 30 dólares. El daño total es 2 + 7 + 11 + 30 = 50 dólares.
Comments
Gracias brother , por cierto podrian agregar este comentario como un editorial para el problema.
Hecho! Moví el comentario hacia editorial.
Como puedo ir haciendo que la Dp me sume la ganancia anterior.