Word Wrap (2) P41723


Statement
 

pdf   zip

thehtml

Vamos a hacer como el (el editor de textos que usamos en la OIE para escribir los enunciados de los problemas): tenemos un texto formado por palabras separadas por espacios, y queremos “cortarlo” en líneas de no más de k letras cada una (el espacio horizontal que tenemos disponible). Sin embargo, a diferencia del Word, no intentaremos ocupar el mínimo número de líneas posible: lo que queremos es evitar que hayan líneas demasiado vacías.

Si tenemos un ancho de k letras, y nuestra línea ocupa sólo tk de esas letras, diremos que la fealdad de la línea es (kt)2. La fealdad de un texto dividido en líneas es la suma de las fealdades de todas sus líneas, excepto la última. Se te pide que calcules, de entre todos los modos de dividir un texto en líneas, la fealdad mínima que es posible conseguir.

Entrada

La entrada de este problema es idéntica a la del problema “Word Wrap (1)”. Es decir, una línea con el número k>0, seguido de un número indeterminado de líneas con palabras (secuencias de letras, dígitos, o signos de puntuación) separadas entre sí por un número arbitrario de espacios y saltos de línea. Se te asegura que ninguna palabra tiene más de k letras.

Se te garantiza que k<100 y que no habrá más de 5000 palabras.

Salida

Escribe una línea con la mínima fealdad que es posible conseguir.

Pista

¡Haber resuelto “Word Wrap (1)” no te servirá de nada para resolver este problema! Deberás hacer un backtracking si aspiras a obtener 50 puntos, y programación dinámica si aspiras a los 100.

Puntuación

  • Easy:  ‍ Entradas con no más de 20 palabras cada una.  ‍50 Puntos ‍
  • Hard:  ‍ Entradas de todo tipo.  ‍50 Puntos ‍
Public test cases
  • Input

    11
    A BB CCC DDDD EEEEE FFFFFF
    A BB CCC DDDD EEEEE FFFFFF
    A BB CCC DDDD EEEEE FFFFFF
    A BB CCC DDDD EEEEE FFFFFF
    

    Output

    115
    
  • Input

    6
    aaa bb cc ddddd

    Output

    10
    
  • Input

    14
    It is a period of civil war.
    Rebel spaceships, striking
    from a hidden base, have won
    their first victory against
    the evil Galactic Empire.
    

    Output

    73
    
  • Input

    35
    It is a period of civil war.
    Rebel spaceships, striking
    from a hidden base, have won
    their first victory against
    the evil Galactic Empire.
    
    During the battle, Rebel
    spies managed to steal secret
    plans to the Empire's
    ultimate weapon, the DEATH
    STAR, an armored space
    station with enough power
    to destroy an entire planet.
    
    Pursued by the Empire's
    sinister agents, Princess
    Leia races home aboard her
    starship, custodian of the
    stolen plans that can save her
    people and restore
    freedom to the galaxy....

    Output

    151
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++