Ejemplo de programa de algoritmo de programación dinámica

[Descripción del problema]

Cierto país ha desarrollado un sistema de interceptación de misiles para defenderse de los ataques con misiles enemigos. Sin embargo, este sistema de interceptación de misiles tiene un defecto: aunque su primer proyectil puede alcanzar cualquier altura, cada proyectil futuro no puede ser más alto que el anterior. Un día, el radar detectó la llegada de misiles enemigos. Debido a que el sistema aún se encuentra en la etapa experimental y solo hay un sistema, es posible que no pueda interceptar todos los misiles.

Ingrese la altitud de vuelo del misil en secuencia (los datos de altitud proporcionados por el radar son un número entero positivo no mayor a 30.000, con al menos un espacio entre cada dato) y calcule el número máximo de misiles. que el sistema puede interceptar si se quieren interceptar todos los misiles, al menos cuántos sistemas de interceptación de misiles deben estar equipados.

[Muestra de entrada-salida]

Entrada:

389 207 155 300 299 170 158 65

Salida:

6 (El número máximo de misiles que se pueden interceptar)

2 (El número mínimo de sistemas que pueden interceptar todos los misiles)

[Análisis de problemas]

Primero resuelve el problema Una pregunta. El número máximo de misiles que un sistema puede interceptar está estrechamente relacionado con la altitud de los misiles que finalmente intercepta. Supongamos que a[i] representa el número máximo de misiles que el sistema puede interceptar cuando el último misil interceptado es el I-ésimo misil. Por ejemplo, un [5] = 3 en la muestra significa que si el último misil interceptado por el sistema es 299, puede interceptar los misiles 0 (389), 4 (300) y 5 (299) como máximo. . Obviamente, el valor máximo entre a[1]~a[8] es la respuesta a la primera pregunta. La clave es cómo encontrar un [1]~a [8].

Supongamos que se ha obtenido a[1]~a[7] (nota: esta suposición a menudo se requiere en la programación dinámica), entonces, ¿cómo encontrar a[8]? A[8] requiere que el último misil interceptado por el sistema sea 65, lo que significa que la altura del penúltimo misil interceptor debe ser no menor a 65, por lo que los misiles que cumplen con los requisitos son 389, 207, 155, 300, 299, 170 y 158. Si el misil en el último segundo es 300, entonces A[8] = A[4] 1; si el penúltimo misil es 299, entonces A[8] = A[5] 1; a[1] 1, a[2] 1,. Por supuesto, lo que estamos buscando ahora es el número máximo de misiles que terminan en 65, por lo que a[8] debería tomar el máximo de todos los valores posibles, es decir, A. [8] = Máx { A[1]1,A[2]1,...,A[7]65448.

Del mismo modo, podemos suponer que se sabe que a[1]~a[6] encuentran a[7]. De manera similar, a[6], a[5], a[4], a[3] y a[2] son ​​soluciones similares, a[1] es 1, es decir, si el último misil interceptado por el sistema Si es 389, entonces solo se pueden interceptar 65438.

De esta forma, el proceso de solución se puede resumir en la siguiente fórmula:

a[1]=1

a[I]= max { a [j] } 1(I gt; 1, j=1, 2,..., i-1, j también satisface: a[j] gt; = a[i])

Finalmente solo Se genera a[1] ~El valor máximo de a[8]. Esta es la solución al primer problema, llamado "programación dinámica".

La segunda pregunta es más interesante. Debido a que sigue a la primera pregunta, la pregunta anterior la influye fácilmente. Es incorrecto utilizar la primera pregunta muchas veces y luego obtener el número total de veces. No es difícil dar contraejemplos. Por ejemplo, la secuencia de altura con una longitud de 7 es "7 5 4 1 6 3 2", y la secuencia no ascendente más larga es "7 5 4 3 2". la secuencia no ascendente más larga varias veces es de tres sistemas. Pero, de hecho, solo se necesitan dos conjuntos para derribar "7 5 4 1" y "6 3 2" respectivamente; Entonces no puedes usar "programación dinámica" para hacerlo.

Entonces, ¿cuál es el enfoque correcto?

El objetivo es derribar todos los misiles con el mínimo número de sistemas, pero no importa cómo se distribuya el número de misiles entre los sistemas. La idea errónea anterior se hereda de la mentalidad de que "un sistema intercepta tantos misiles como sea posible" e ignora el número relativamente par de intercepciones de cada sistema en la solución óptima. Es esencialmente un algoritmo codicioso, pero la estrategia codiciosa es incorrecta. Si ninguno de los misiles interceptados por cada sistema funciona, entonces cambia la idea y comienza con el sistema seleccionado para interceptar un determinado misil.

La pregunta nos dice que la altura de puntería actual del sistema existente no debe ser inferior a la altura de puntería del misil entrante, por lo que cuando el sistema existente no puede interceptar el misil, se debe activar un nuevo sistema. . Si un sistema existente puede interceptar misiles, ¿debería seguir usándose o reinventarse? El hecho es que no importa qué sistema se utilice, siempre que el misil sea interceptado, la altura de apuntamiento del sistema es igual a la altura del misil, y esto se aplica tanto a los sistemas nuevos como a los antiguos. El nuevo sistema puede interceptar misiles a la mayor altitud, lo que significa que el rendimiento del nuevo sistema es mejor que cualquier sistema que se haya utilizado. En este caso, sin duda deberíamos elegir el sistema existente. Si existen múltiples sistemas que pueden interceptar misiles, ¿cuál deberíamos elegir? Actualmente, los sistemas que apuntan a gran altitud tienen un mayor "potencial", pero los sistemas que apuntan a baja altitud son diferentes. Los misiles que puede disparar también pueden ser disparados por otros sistemas, pero los misiles que no puede disparar no son necesariamente los que otros sistemas no pueden disparar. Por lo tanto, cuando hay varios sistemas para elegir, se debe seleccionar el que tenga la altura de puntería más baja. Por supuesto, la altura de puntería debe ser mayor o igual a la altura del misil entrante.

Al resolver el problema, utilice un sistema de matriz para anotar la altura de puntería actual del sistema existente. El número real de elementos en la matriz es la respuesta a la segunda pregunta.

[Programa de referencia]

Programa noip 1999 _ 2;

const max = 1000

var i, j, current, maxlong, minheight, select, tail, total: longint;

Altura máxima, sys: matriz [1..max] de longint;

Fila: cadena;

Inicio

write('Ingresar datos de prueba:');

readln(line); {cadena de entrada}

I: = 1;

Total: = 0; {Número de misiles que ingresan}

Y yo lt= longitud(línea) {desgloso varios números y los almaceno en una matriz de altura}

Iniciar

mientras(i lt=length(line)) y (line[I]= ' ')do I:= I 1; ; {registrar la altura del misil}

while(i lt=length(line)) y (line[I] lt; gt)hacer {convertir la cadena en un número}

Inicio

actual:= actual * 10 ord(line[I])-ord(' 0 ');

i:=i 1

Fin;

Total: =Total 1;

Altura [Total]: =Actual {almacenado en altura}

Fin;

Longest[1]:= 1;{La siguiente es la primera pregunta de programación dinámica}

Para i:=2 hacer el total

Iniciar

maxlong := 1;

para j:=1 a i-1

iniciar

si altura[i] lt;=altura[ j]

Entonces si más largo[j] 1 gt;maxlong

Entonces maxlong:= más largo[j] 1;

Más largo[I]:= maxlong {El número máximo de misiles que pueden ser interceptados después del misil I}

Fin

Fin

maxlong:= más largo[1];

Para i:=2 hacer el total

if más largo[I] gt; maxlong entonces maxlong:= más largo[I];

writeln(maxlong); primera pregunta}

sys[1]: = altura[1]; {Haga la segunda pregunta a continuación}

Cola: = 1; {Subíndice de matriz, y finalmente el número de sistemas requerido}

Para i:=2 para hacer el total

Inicio

altura mínima:= maxint;

Para j: = 1 to tail do {encontrar el sistema más adecuado}

if sys[j] gt; then height[i]

if sys[j] lt entonces Solo el más pequeño

begin min height:= sys[j]; select:= j end;

Si minheight = maxint {Abrir un nuevo sistema}

Entonces comienza tail:= cola 1; sys[cola]:=altura[i]end

else sys[select]:=altura[i]

>

Fin;

writeln(tail)

Fin.

[Parte de los datos de la prueba]

Entrada 1: 300 250 275 252 200 138 245.

Salida 1:

Cinco

2

Entrada 2: 181 205 471 782 1033 1058 111.

Salida 2:

1

Siete

Entrada 3: 465 978 486 476 324 575 384 278 214 657 218 445 123 .

Salida 3:

Siete

Cuatro

Entrada 4: 236 865 858 565 545 455 656 844 735 638 652 659 714 845 .

Resultado 4:

Seis

Siete

¿Es lo suficientemente detallado?