Cómo implementar una cola monótona en Java
Las colas monótonas pueden tener dos operaciones:
1. Insertar un nuevo elemento. El elemento comienza desde el final de la cola, busca hasta el principio de la cola y encuentra un elemento adecuado. posición para insertar. Si había un elemento en esa posición, reemplace ese elemento.
2. En el proceso de eliminación de elementos que no cumplen con los requisitos actuales del encabezado de la cola.
La implementación de una cola monótona puede ser muy sencilla o muy compleja. Una matriz simple, un puntero de cabeza y cola son suficientes. Las implementaciones complejas requieren una lista doblemente enlazada.
Usos:
1. Guardar soluciones óptimas, soluciones subóptimas, etc.
2. El uso de una cola monótona para optimizar la ecuación dp puede reducir la complejidad de O (n) a O (1). En otras palabras, el dp N-dimensional que de otro modo expiraría debe optimizarse hasta N-1 dimensiones para pasar. Este es el problema que quiero ilustrar
¿Se puede optimizar cualquier DP utilizando colas monótonas? La respuesta es no.
¡Por favor recuerda! Solo los DP de la forma dp[i]=max/min (f[k]) g[i] (klt;i amp; amp; g[i] es una variable independiente de k) se pueden optimizar utilizando colas monótonas.
El objeto de optimización es f[k].
Profundiza tus sentimientos a través de ejemplos
/problem.php?pid=1685
Quiero crecer
Descripción
Papá Han tiene N hijos, Han 1, Han 2...Han N. Debido a las magníficas habilidades de actuación y la cooperación tácita de la familia Han, la obra se hizo muy popular. El espectáculo fue un gran éxito, llegando incluso a recaudar 20 millones en taquilla. Zhou Zi es un publicista muy prestigioso, pero en la superficie es limpio y honesto, pero por dentro es oscuro. Al ver la prosperidad de la familia Han, se siente celoso, por lo que publica en Weibo para burlarse de la familia Han sobre sus desigualdades. están parados en fila. Debido a la influencia de Zhouzhou, una palabra casual causará grandes pérdidas a la familia Han. Las pérdidas específicas se calculan de la siguiente manera: Han Uno, Han Dos... Han N están en una fila, y la pérdida es C* (Han La altura. diferencia entre i y Han i 1 (1lt; = ilt; N)), y tal vez incluso la hija se haya ido. El padre Han pensó mucho y decidió aumentar la altura de los hijos de la familia Han (tenga en cuenta que no es científico que los hijos de la familia Han sean más bajos. Solo pueden aumentar la altura o no hacer nada). la altura en 1 cm, pero costará mucho dinero aumentar la altura en 10 cm. Para cualquier Han i, cuesta H^2 aumentar Hcm. Ayude al padre Han a minimizar la pérdida de la familia Han.
Entrada
Hay varios conjuntos de datos a procesar hasta el final del archivo. La primera línea de cada conjunto de datos son dos números enteros: el número de caracteres chinos N (1lt; =Nlt; =50000) y el coeficiente del barco C (1lt; =Clt; =100). alturas del pueblo Han i(1lt;=hilt;=100).
Primero, establezca la ecuación. Es fácil pensar en dp[i][j] como el costo más bajo para sub-i con altura j. Al analizar el problema, no es difícil saber que el costo de altura del hijo actual solo se ve afectado por el del hijo anterior. Por lo tanto,
dp[i][j]=min(dp[i-1][k] abs(j-k)*C (x[i]-j)*(x[i]-j )); donde x[i] es la altura original del i-ésimo hijo
Analicemos la complejidad.
Primero, hay N nodos secundarios, lo que requiere un bucle. Además, cada hijo tiene una altura de 0 a 100, lo que también requiere una dimensión. Luego, cada altura de 0 a 100 se puede derivar recursivamente de la altura del hijo anterior de 0 a 100.
Por lo tanto, la complejidad temporal del algoritmo ordinario es O(n^3). A la pregunta solo se le dan dos segundos, ¡lo cual es inaceptable!
Ecuación analítica:
Cuando el hijo i-ésimo es más alto que el hijo i-1,
dp[i][j] = min( dp [i-1][k]j*C - k*C X); (klt;=j) donde X = (x[i]-j)*(x[i]-j).
Cuando la altura del i-ésimo hijo es más corta que la altura del i-1 hijo,
dp[i][j]=min(dp[i-1 ][ k] - j*C k*C k]-k*C, g[i][ j]=j*C X Por lo tanto dp[i][j] = min (f[i-1][k] ) g[i][j]. Convertido a este formulario, podemos usar colas monótonas para la optimización.
La segunda ecuación es la misma.
El siguiente paso es cómo implementarlo, lo cual es un poco complicado. Ver
Ver código
Otro tema que es útil para comprender los métodos de optimización es HDU 3401/showproblem.php?pid=3401
Este tema es más o menos Esto es así: una persona conoce las condiciones del mercado de valores en T días en el futuro y quiere saber cuánto dinero puede ganar al final.
Construya el estado dp[i][j], indicando cuánto dinero ganó cuando poseía acciones j el día i
Las transiciones de estado son:
1, No hay operaciones desde el día anterior:
dp[i][j]=max(dp[i-1][j], dp[i][j])
2, comience a comprar algunas acciones del día anterior i-W-1 días:
dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP [i], dp[ i][j])
3. Vender algunas acciones del día i-W-1:
dp[i][j]=max(dp[i-W). -1][k ] (k-j)*BP[i], dp[i] [j])
Aquí es necesario explicar por qué es suficiente considerar solo las ventas de los días i-W-1 . Piénselo, si no compra ni vende el día i-W-2, ¿no podría transferir su mejor estado al día i-W-1? Por analogía, no es necesario considerar las anteriores, solo se consideran todas las situaciones del día i-W-1.
Analice la situación de compra de acciones y conviértala en una ecuación adecuada para la optimización de colas monótonas
dp[i][j]=max(dp[i-W-1][ k ] k*AP[i])-j*AP[i]. Supongamos f[i-W-1][k] = dp[i-W-1][k] k*AP[i], luego dp[i][j] = max(f[i-W-1][k]) -j *AP[i].
De esta manera, se pueden utilizar colas monótonas para la optimización. El análisis de la venta de acciones es similar.
Ver código
Finalmente, hay otra aplicación que puede usar colas monótonas para optimizar el problema de mochilas múltiples hdu 2191
Si hay n elementos, el El precio es w, el peso es c y la cantidad de cada artículo es k, entonces el valor de la mochila resultante se puede maximizar cargando en ella varios de estos artículos con una capacidad m.
Una forma de optimizar el problema de múltiples mochilas es utilizar la optimización binaria, cuya complejidad temporal es O(m*∑log k[i]), consulte
blogs.com/ ka200812/archive/2011/08/06/2129505.html
La complejidad de usar el método de optimización de cola monótona es O(mn)
Primero, para el i-ésimo elemento, Si se sabe que su volumen es V, su valor es W y su cantidad es K, el volumen actual J se puede dividir en V grupos según los residuos de V (0, 1, ....V-1) .
Para cualquier grupo, se puede obtener la ecuación de transferencia: f[i*V c]=f[k*V c] (i-k)*W, donde c es cualquier grupo del grupo V< / p>
Cuando f[i*V c]=dp[i], obtienes dp[i]=dp[k] (i-k)*W (kgt;=i-K)
Usando dp [k]-k*W como función de optimización, puedes aplicar una cola monótona para optimizarla