Cómo implementar una cola monótona en Java

Las colas monótonas pueden tener dos operaciones:

1. Busque elementos desde el final de la cola hasta el principio de la cola, busque la posición adecuada e insértelo. Si hay un elemento en esta posición, reemplácelo.

2. Durante este proceso se eliminan elementos del líder del equipo que no satisfacen las necesidades actuales.

Las colas monótonas son simples y complejas de implementar. Una matriz simple con un puntero de cabeza y cola será suficiente. Lista compleja doblemente enlazada.

Utilice:

1 para guardar la solución óptima, la solución subóptima, 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 se suponía debía expirar debe optimizarse a N-1 dimensiones antes de que pueda pasar. Esto también es algo que quiero registrar.

¿Se puede optimizar cualquier DP utilizando una cola monótona? La respuesta es no.

¡Recuerda! Solo la forma DP [I] = max/min (f [k]) + g [I] (k

El objeto de optimización es f[k].

Profundizar sentimientos a través de ejemplos

/problem.php? pid=1685

Quiero crecer

Descripción

Hanbok tiene n hijos, respectivamente, Han Yi, Han Er... Han N, debido a las profundas habilidades de actuación y la estrecha cooperación de la familia Han, la actuación fue un gran éxito y la taquilla incluso alcanzó los 20 millones. , pero es muy limpio en la superficie, de hecho, su corazón estaba oscuro y se puso celoso cuando vio la prosperidad de la familia coreana, e hizo comentarios modestos sobre la altura desigual de los dos coreanos parados en una fila. Una sola frase causará grandes pérdidas a las familias coreanas. La pérdida específica se calcula de la siguiente manera: Han 1, Han 2... Han N está en una fila y la pérdida es C* (la diferencia de altura entre Han 1 y Han 1). +1 (1

Entrada

Hay varios conjuntos de datos, que se procesan 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 (1

En primer lugar, se establece la ecuación. Es fácil pensar que dp[i][j] representa el costo de altura más bajo del I-ésimo hijo. Es fácil para saber que el costo de altura del hijo actual solo se ve afectado por el 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. /p>

Primero, hay n hijos, lo que requiere un ciclo, y la altura de cada hijo es de 0 a 100, lo que también requiere una dimensión. Además, cada altura de 0 a 100 se puede derivar de forma recursiva. altura anterior de 0 a 100.

Entonces, la complejidad temporal del algoritmo ingenuo es O (n 3, lo cual es inaceptable).

Cuando la altura del i-ésimo hijo es mayor que la altura del i-1º hijo,

DP[I][j]= min(DP[I-1][k] +j * C-k * C+X); (k & lt=j)donde X=(x[i]-j)* (x[i]-j

Cuando la altura del. El i-ésimo hijo es más corto que la altura del i-1º hijo,

DP[I][j]= min(DP[I-1][k]-j * C+k * C +X); (k & gt=j)

Para la primera ecuación, sea f[I-1] [k]= DP[I-1][k]-k * c, g[ I][j]= j * c+x; entonces DP[I][J]= min(F[I-1][ K])+G[I][J]. una cola monótona.

La segunda ecuación es la misma.

El siguiente paso es cómo implementarlo, lo cual es un poco complicado. Consulte a continuación para obtener más detalles.

Ver código

¿Otro tema adecuado para comprender este método de optimización es HDU 3401/showproblem.php? pid=3401

La pregunta general es: una persona conoce el mercado de valores en T días en el futuro y quiere saber cuánto dinero puede ganar al final.

El estado de apertura de la posición dp[i][j] indica cuánto dinero ganó cuando poseía acciones J el día I.

Las transiciones de estado incluyen:

1. No compré ni vendí el día anterior:

dp[i][j]=max(dp[i -1][j], dp[i][j])

2. Compre algunas acciones de i-W-1 hace 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])

Requerido aquí Explicar por qué solo se consideran las ventas y compras en i-W-1. Piénselo, ¿puede i-W-2 transferir su mejor estado al primer día de i-W-1 sin comprar ni vender? Por analogía, no es necesario considerar los anteriores, solo se considera la situación del día i-W-1.

La situación de compra de acciones se analiza y se transforma 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]. K]= DP[I-W-1][K]+K * AP[I], luego DP [I] [J] = Max (F [I-W-1] [

Esto puede usar un monótono cola Para optimizar La situación de venta de acciones es similar

Ver el código

Finalmente, hablemos de una aplicación que utiliza la cola monótona para optimizar el problema de mochila múltiple hdu 2191.

Si hay uno. n artículos, el precio de cada artículo es W, el peso de cada artículo es C y la cantidad de cada artículo es K, entonces llena una mochila con una capacidad M con tal. elementos para maximizar el valor de la mochila. Este problema es el problema de las mochilas múltiples.

Para el problema de las mochilas múltiples, un método de optimización es utilizar la optimización binaria. La complejidad temporal de este método de optimización es O (m). *∑log k[i]), como se muestra

blogs.com/ka 200812/archive/2011/08/06/2129505.html

La complejidad de la optimización de colas monótonas. es O(mn).En primer lugar, para el elemento I, si el volumen es V, el valor es W y la cantidad es K, entonces el volumen actual J se puede dividir en V grupos (0, 1,...V-1) según el resto de v

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 V grupos.

Supongamos f[i*V+c]=dp[i], entonces obtenemos DP[I]= DP. [k]+(I-k)* W(k & gt; =i-K)

Si dp[k]-k*W se considera una función de optimización, entonces se puede utilizar una cola monótona para la optimización.