Turismo
Estás planeando un viaje para visitar N atracciones turísticas. Las atracciones están numeradas del 1 al N y deben ser visitadas en ese orden. Puedes visitar a la sumo K atracciones por día y deseas planificar el viaje tomando el menor número de días posible.
Bajo estas restricciones, usted desea encontrar un esquema que tenga un buen equilibrio entre las atracciones visitadas cada día. Para ser precisos, asignamos una puntuación a la atracción i. Dado un esquema, cada día se da un puntaje igual al puntaje máximo de todas las atracciones visitadas ese día. Finalmente, las puntuaciones de cada día se suman para dar el puntaje total del esquema. ¿Cuál es el máximo total posible del esquema, usando el menor número de días posible?
Especificación de entrada
La primera línea contiene dos enteros separados por espacios N y K . La siguiente línea contiene N enteros separados por espacios .
Especificación de salida
Un simple entero, el máximo valor posible.
Ejemplo de entrada
5 3
2 5 7 1 4
Ejemplo de salida
12
Explicación:
Necesitamos al menos dos días para visitar las todas atracciones puesto que en un día no se pueden visitar todas. Visitando las dos primeras atracciones en el día 1 tendremos una puntuación de 5 y visitando las últimas tres atracciones el día 2 tendremos una puntuación de 7 para una puntuación total de 12.
Visitando las tres primeras atracciones el día 1 y las otras dos el día 2, lo cual es también posible en esta menor cantidad de días, nos da una puntuación de 7 + 4 = 11.
Comments
gracias por la aclaracion
tomar el menor numero de días posibles quiere decir q va a existir n/k días q visita k atracciones y un día q visita n%k atracciones???
No, significa que son días. Por ejemplo, cuando , el primer día puede terminar en cualquier atracción , y entonces el segundo día empieza en ; solo hay dos recorridos que cumplen lo que dices: cuando y cuando , es posible que ninguno de ellos sea la solución óptima; por ejemplo: asumamos que y que , y son menores que todos los demás elementos del arreglo, entonces el recorrido \(1—2\) para el primer día y \(3—\dots —n\) para el segundo día es mayor que el recorrido para el primer día y \(2—\dots —n\) para el segundo día, y también es mayor que el recorrido \(1—\dots—k\) para el primer día y para el segundo día