Descripción del problema
Hay un puente de una sola tabla en el río. Una rana quiere saltar de un lado del río al otro a lo largo del puente de una sola tabla. Hay algunas piedras en el puente. La rana odia pisar estas piedras. Dado que la longitud del puente y la distancia que salta la rana al mismo tiempo son números enteros positivos, podemos pensar en los posibles puntos donde la rana puede llegar en el puente de una sola tabla como una serie de números enteros en el eje numérico: 0, 1,..., L (donde L es la longitud del puente). El punto con coordenada 0 representa el punto inicial del puente y el punto con coordenada L representa el punto final del puente. La rana comienza desde el punto inicial del puente y sigue saltando hasta el punto final. La distancia de un salto es cualquier número entero positivo entre S y T (incluidos S, T). Cuando la rana salta o salta sobre el punto con coordenada L, se considera que la rana ha saltado del puente de una sola tabla.
La pregunta da la longitud L del puente de una sola tabla, el rango de distancia S, T del salto de la rana y la posición de las piedras en el puente. Tu tarea es determinar la cantidad mínima de piedras que la rana debe pisar para cruzar el río.
Para el 30% de los datos, L?<=?10000; para todos los datos, L?<=?10^9. <=?10^9<=?10^9<=?10^9<=?10^9<=?10^9<=?10^9=?10^9
Entrar
La primera línea de entrada contiene un entero positivo L (1?<=?l?<=?10^9), que representa la longitud del puente de una sola tabla. La segunda línea tiene tres números enteros positivos S, T, M, que representan respectivamente la distancia mínima, la distancia máxima del salto de una rana y el número de piedras en el puente, entre las cuales 1?<=?s?<=?t ?<=?10 ,1?<=?m?<=?100. La tercera línea tiene M números enteros positivos diferentes que representan las posiciones de las M piedras en el eje numérico (los datos aseguran que no hay piedras en el punto inicial y final del puente). Todos los números enteros adyacentes están separados por un espacio. <=?m?<=?100<=?m?<=?100<=?m?<=?100<=?m?<=?100<=?m?<=?100<=?m? <=?100=?M?<=?100
El algoritmo del problema en sí no es difícil. Es un problema de programación dinámica para encontrar el número mínimo de piedras en el punto de partida de atrás hacia adelante. para Frog Crossing the River, en línea Se pueden encontrar muchas publicaciones. Pero esto no es suficiente. En primer lugar, cuando la cantidad de datos es grande, la memoria explota directamente, por lo que los datos deben comprimirse y fragmentarse. El otro es un caso especial si se requiere el número mínimo de pasos. El número máximo de pasos de la rana es igual, calcula directamente. Eso es todo.
Aquí registro principalmente cómo comprimí. La idea principal es la siguiente: primero, clasifique las posiciones de las piedras y luego recorra de atrás hacia adelante si se encuentra que la distancia entre las dos piedras. demasiado largo, luego obtenga un fragmento comenzando con la siguiente piedra y luego calcule la cantidad mínima de piedras que pasan a través de este fragmento. Al final, el número mínimo de piedras en todo el puente de una sola tabla es la suma de los resultados de todos los fragmentos.
Entonces la pregunta ahora es: ¿cómo se puede considerar que la distancia entre las piedras es lo suficientemente larga? Si los números maxStep anteriores son todos iguales, entonces no importa cómo avance, todos serán el mismo número y la distancia que puede garantizar que los números anteriores se conviertan en el valor mínimo, mi idea es relativamente simple y burda; similar a la clasificación de burbujas La idea es algo cercana, es decir, suponiendo que el último valor (el valor en la posición maxStep-1) es el valor mínimo, luego avanza posiciones (maxStep-minStep) en cada ronda. Se supone que la longitud de cada ronda es maxStep, por lo que se necesitan (maxStep - 1)*maxStep/(maxStep-minStep) para pasar a la primera posición. Por lo tanto, si la distancia entre dos piedras excede este valor, entonces calcule directamente el número mínimo de piedras en cada posición de este fragmento y luego tome el valor mínimo de los valores maxStep anteriores.
Finalmente, si llegas al inicio del segmento, si la primera piedra aún está lo suficientemente lejos del punto inicial, podrás calcularlo de la misma manera. Sin embargo, si la primera piedra está muy cerca. El punto de partida, puedes calcularlo directamente hasta el punto de partida. El número mínimo de piedras es suficiente.