¡Explicación detallada de la programación dinámica por 200 puntos! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !

Mira lo que escribió sobre la ausencia de efectos secundarios y la subestructura óptima. Es una cabeza grande, y yo también...

Dinámico. La programación generalmente resuelve dos tipos de problemas. Uno son los problemas de optimización, que le piden los números máximos y mínimos, y el otro es el número total de soluciones.

Hay muchos tipos de subdivisiones,

He visto muchas de ellas (soy un estudiante de segundo año y actualmente me preparo para NOIP).

Si tienes demasiadas preguntas, simplemente las diré por su nombre.

Mochila, incluso la novena conferencia se ha puesto arriba, así que no diré más...

El problema de subsecuencia no ascendente y no descendente más largo (como Pampas Xiong El vuelo del juego de simulación Eagle Birthday es una deformación clásica que no cae)

Problemas de asignación de recursos (como disposición de ventanas, problemas de estabilidad, problemas de asignación de máquinas)

Homing a intervalos ( producto máximo, collar de energía, etc.)

El problema de subsecuencia común más largo (parece tener un código genético);

Solución al árbol, como subir escaleras... ... ...

Existen muchos tipos de programación dinámica porque es muy flexible. Una vez, nuestro profesor encontró 100 ecuaciones del PD, pero todas eran inútiles. No podemos aprender de memoria. La clave es entenderlos.

Un poco más profundo es la optimización de DP, la reducción de dimensionalidad del tiempo y el espacio (es decir, usar otros métodos para hacerlo, o por ejemplo, la mochila es originalmente bidimensional y debería ser unidimensional). dimensional), y árbol DP (esto tampoco lo haré).

(Hay un tema clásico en optimización "cruzar el río")

Soy una de esas personas que de repente domina el conocimiento de DP... No digas "Programación dinámica", en realidad es una comparación y un cálculo. Si sabes lo que hizo, tendrás una pista, una ecuación y una idea...

Lo principal es leer más preguntas, empezar con las sencillas y comprender sus ideas... Paga atención cuando escribes las siguientes preguntas:

1. La premisa es asegurarte de que lo que estás haciendo avanza hacia el tema... si lees más, sabrás qué tipo de tema. estás enfrentando.

2. La segunda premisa es que la idea debe ser correcta (cuando hago el problema, primero pienso en la dimensión espacio-temporal del problema y luego pienso en la ecuación en consecuencia), y la la ecuación es correcta.

Realmente no recuerdo que primero puedo ver la solución al problema y, después de comprender las ideas de otras personas, puedo hacer el programa sin mirar el proceso estándar...

3. Tenga cuidado de no hacerlo. La matriz es demasiado pequeña. En términos generales, las matrices deberían ser más grandes en los lados izquierdo y derecho. Por ejemplo, si su rango de datos es 1~100, la matriz será 0~101. Esto es para evitar límites, porque muchos DP usan F al asignar valores iniciales.

4. El valor inicial debe ser correcto, porque muchos DP son correctos en otros lugares. Es muy común que todos los DP fallen debido a valores iniciales incorrectos... (como el sistema monetario de USACO).

5.El rango del bucle DP debe ser correcto. Generalmente, la cantidad de escritura se juzga según el tema (por ejemplo, el problema de la ventana, no pude escribir este tema esta tarde porque el ciclo estaba mal).

USACO también tiene muchas preguntas sobre el PD que puedes hacer...

Las anteriores se hacen todas manualmente, espero que pueda ayudarte.

También soy una persona que está aprendiendo. Nada de lo anterior es necesariamente correcto, pero a mí me funciona y esta es mi experiencia.

Espero que podamos aprender, comunicarnos y progresar juntos en el futuro

QQ:340131980

1 Problema de recursos 1

-Problema de asignación de máquinas

f:=verdadero; g:=falso; g:=falso;

g:=0

f+sqr(len(j)+k),

f}

Respuesta:=f

21. Programación dinámica lineal 3

-Subcadena común más larga, problema LCS

f:=max(f, f);

f:= sigma(f);

Programación dinámica de 51 árboles

Guardia del Palacio

f:=max(f,f);

f:= sigma(f);

52 Mundo Recursivo

-Box y Ball

f:=1

Programación dinámica de 57 árboles

K-medias problema de árboles dirigidos

F:=min{ f +palabras[s], f+palabras, l-R]);

Si (j=k) y (k=l) entonces inc(f]+a]

94 Programación dinámica

-noi 2004 berry linear

f .

Optimización de estado: g[i, j]=min{g[i-1, j] , g[i-1, j-1]+long}

Donde (a, b)+long = (a', b') se calcula de la siguiente manera:

Cuando b+long ≤t: cuando a'=a; b'= b+ long;

Cuando b+long > t: a ' = a+1; b'= long;

Condiciones de límite planificadas:

Cuando 0≤i≤n, g=(0,0)

98 Programación dinámica

- AHOI 2006 Treasure Channel

f[k]:=max{f[k-1]+x[k,j]-x[k,i-1],x[k,j]-x[k,i-1 ] }

99 Programación Dinámica

-Viajes

a) El plan de viaje más económico.

Supongamos que f representa el costo mínimo de estadía en el I-ésimo hotel desde el punto de partida; g representa el número mínimo de días desde el punto de partida hasta el I-ésimo hotel en un día, siempre que el Se alcanza el costo mínimo. Entonces:

f=f[x]+v, g=g[x]+1

x satisface:

1, x & ltI, y d–d[x]<=800 (carrera máxima en un día).

2. Para todo T

A.g[x]<G[t] (cuando f[x] = f[t]) b.f[x]

f[0] = 0, g[0] = 0.Respuesta:=f[n + 1], g[n+1].

b) Plan de viaje con el menor número de días.

En realidad, el método es muy similar a la primera pregunta.

Supongamos que g' representa el número mínimo de días desde el punto de partida hasta el I-ésimo hotel; 'f' se refiere al costo mínimo de permanecer en el I-ésimo hotel durante un día desde el punto de partida. , siempre que se cumpla el número mínimo de días. Entonces:

g' = g'[x] + 1, f' = f'[x] + v

x satisface:

1, x & ltI, y d–d[x]<=800 (ictus máximo en un día).

2. Para todo T

f '[x]& lt; cuando f'[t] g'[x] = g'[t]

g '[x]<Otros casos

f'[0] = 0, g'[0] = 0. Respuesta:=f'[n + 1], g'[n +1 ].

100 Programación Dinámica

- NOI 2007 Efectivo

y:= f[j]/(a[j]* c[j] +b [j]);

g:= c[j]* y * a+y * b;

f:=max(f,g)