Gracias por A2A, Nick. ( Sé que sabes cómo resolver este problema).
En primer lugar, hay una larga discusión sobre las soluciones de programación dinámica La respuesta de Brian Bi a ¿Cuál es la propiedad de la monotonía con respecto a la programación dinámica? Apuesto a que hay una manera de obtener O (n log n) con este enfoque DP, pero actualmente se me escapa.
Sin embargo, sé cómo hacerlo con un algoritmo codicioso que aprendí de un problema en el campamento de USACO en 2009. (CCROSSX es una generalización de ese problema). Aquí está:
- ¿Qué escenario aplica algoritmo y estructura de datos?
- ¿Qué es el algoritmo k-Nearest Neighbour? ¿Qué tipo de problemas puede resolver este algoritmo? ¿Qué tipo de matemática se requiere?
- ¿Cómo entender el algoritmo SHA-1? ¿Cuáles son los mejores ejemplos para ello?
- Ahora he leído sobre algoritmos y estructuras de datos como Al Klein me dijo. ¿Qué lenguaje de programación debo aprender?
- ¿Cuál es el algoritmo de clave pública y privada?
Vamos a dejar que [math] h_0, \ dots, h_ {n-1} [/ math] sea la secuencia de entrada, las alturas en relación con las cuales se medirá el costo de la configuración final.
Ahora, comience imaginando que ha establecido las alturas en [matemáticas] g_i = h_0 – di [/ matemáticas], es decir, [matemáticas] h_0, h_0 – d, h_0 – 2d, \ puntos, h_0 – (n-1 ) d [/ matemáticas]. La secuencia de diferencias consecutivas es [matemática] -d, -d, \ puntos, -d [/ matemática]. Es decir, hemos hecho todas las alturas lo más bajas posible. Vamos a subir las alturas hasta que la última altura sea en [math] h_ {n-1} [/ math], donde debe estar en la configuración final.
Ahora, en cada paso, vamos a tomar una de las diferencias y aumentarla en 1 ( por ejemplo , en el primer paso, aumentaremos una de las diferencias de -d a -d + 1). Esto equivale a elegir un pilar, luego aumentar la altura de ese pilar y cada pilar a la derecha en 1.
Además, elegiremos el pilar (de todos los pilares viables) de modo que al hacerlo disminuya la función de costo en la mayoría. Un pilar no es viable si elegirlo causaría que una de las diferencias sea mayor que d.
Realiza este paso un número fijo de veces; cada vez que lo haces, el último pilar aumenta la altura en 1, y te detienes cuando alcanza la altura [matemática] h_ {n-1} [/ matemática].
Te lo dejo para que demuestres que esto es correcto. (Soy perezoso.)
Implementar esto en O (n log n) es otro problema. La primera observación es que cuando eliges un pilar, no solo lo levantas por 1, sino que lo levantas tanto como puedes antes de que el pilar óptimo cambie. (Esto ocurriría siempre que algún pilar sobrepase [math] h_i [/ math]).
Ahora, puede hacer esto con un árbol de rango, pero tiene que rastrear mucha información:
- Para cada pilar, la cantidad que la función de costo disminuiría si elige ese pilar. Debe poder consultar el óptimo, entre todos los pilares viables , por lo que también debe realizar un seguimiento de cuáles son viables.
- Debe poder detectar cuándo un pilar supera su [matemática] h_i [/ matemática], para que pueda mantener los datos anteriores actualizados. Por lo tanto, debe realizar un seguimiento: para cada pilar, si actualmente está por encima o por debajo de [math] h_i [/ math] y cuánto tiempo más pasará antes de que supere [math] h_i [/ math]. Debe poder consultar el próximo pilar que vaya por encima de su [math] h_i [/ math] si comienza a levantar todos los pilares en un rango particular.
Creo que este es el problema de árbol de rango más complicado que he hecho.
