¡Busque preguntas de programación dinámica para obtener puntuaciones altas! ! !
Este es el curso experimental del Curso de Diseño de Algoritmos de nuestro Departamento de Informática. El siguiente es el contenido de programación dinámica:
Experimento 4: Programación Dinámica
<. p>Propósito del experimento: Comprender la programación dinámica La idea básica es comprender las propiedades óptimas de la subestructura y las propiedades superpuestas de los subproblemas, dos elementos básicos del algoritmo de programación dinámica. Ser competente en problemas típicos de programación dinámica. Dominar el método general de análisis de problemas con ideas de programación dinámica, ser capaz de analizar correctamente problemas más simples, diseñar algoritmos de programación dinámica y poder implementarlos rápidamente a través de la programación.Contenido experimental: Programación para implementar los problemas de ejemplo mencionados: problema de subsecuencia común más larga, problema de multiplicación de matrices, problema de triangulación óptima de polígonos convexos, problema de cableado de circuitos, etc. Para los problemas de este experimento, el algoritmo fue diseñado e implementado en programación.
Ejercicios
1. La subsecuencia común más larga
La subsecuencia de una secuencia dada es la secuencia obtenida eliminando varios elementos de la secuencia. Para ser precisos, si la secuencia dada X=lt; La secuencia índice lt; i1, i2,..., ikgt;, de modo que para todos j=1, 2,..., k, hay
La solución es la siguiente:
a) Común más largo ** *La estructura de la subsecuencia
Si se utiliza el método de búsqueda exhaustiva, llevará demasiado tiempo y el algoritmo requiere un tiempo exponencial.
Es fácil demostrar que el problema de subsecuencia *** común más largo también tiene propiedades de subestructura óptimas
Supongamos que la secuencia X=lt; y Y=lt; Una subsecuencia común más larga de y1, y2,…, yngt; Z=lt; z1, z2,…, zkgt;, entonces:
i. xm=yn y Zk-1 es la subsecuencia común más larga de Xm-1 e Yn-1;
ii. Si xm≠yn y zk≠xm, entonces Z es la suma de La subsecuencia común más larga de Y;
iii. Si xm≠yn y zk≠yn, entonces Z es la subsecuencia común más larga de X e Yn-1.
Donde Xm-1=lt; z2,…, zk-1gt;.
El problema de subsecuencia común más largo tiene propiedades de subestructura óptimas.
b) Estructura recursiva de subproblemas
A partir de las propiedades óptimas de la subestructura del problema de subsecuencia común *** más largo, necesitamos encontrar X=lt; ., xmgt; y Y=lt;y1, y2, ..., yngt; La subsecuencia común más larga se puede realizar de forma recursiva de la siguiente manera: cuando xm=yn, encuentre Xm-1 e Yn-1 La subsecuencia común más larga de X, y luego agregue xm (=yn) al final para obtener la subsecuencia común más larga de X e Y. Cuando xm≠yn, se deben resolver dos subproblemas, a saber, encontrar una subsecuencia común más larga de Xm-1 e Y y una subsecuencia común más larga de X e Yn-1. La más larga de estas dos subsecuencias comunes es la subsecuencia común más larga de X e Y.
A partir de esta estructura recursiva, es fácil ver que el problema de subsecuencia común más largo tiene subproblemas superpuestos. Por ejemplo, al calcular la subsecuencia común más larga de X e Y, es posible que necesite calcular la subsecuencia común más larga de X e Yn-1 y Xm-1 e Y. Ambos subproblemas contienen un subproblema común, que es calcular la subsecuencia común más larga de Xm-1 e Yn-1.
Establezcamos la relación recursiva de los valores óptimos de los subproblemas. Utilice c[i,j] para registrar la longitud de la subsecuencia común más larga de las secuencias Xi e Yj. Donde Xi=lt; x1, x2,…, xigt;, Yj=lt;
Cuando i = 0 o j = 0, la secuencia vacía es la subsecuencia común más larga de Xi e Yj, por lo que c [i, j] = 0. La relación recursiva se establece de la siguiente manera:
c) Calcular el valor óptimo
Dado que en el espacio de subproblemas considerado solo existen θ(m*n) subproblemas diferentes Por lo tanto, el uso de un algoritmo de programación dinámica para calcular el valor óptimo de abajo hacia arriba puede mejorar la eficiencia del algoritmo.
El algoritmo de programación dinámica LCS_LENGTH(X, Y) para calcular la longitud de la subsecuencia común más larga se basa en la secuencia X=lt; y1, y2,…, yngt; Genere dos matrices c[0..m, 0..n] y b[1..m, 1..n]. Entre ellos, c [i, j] almacena la longitud de la subsecuencia común más larga de Xi e Yj, y b [i, j] registra la solución de subproblema mediante la cual se alcanza el valor de c [i, j]. al construir la subsecuencia común más larga. Finalmente, la longitud de la subsecuencia común más larga de X e Y se registra en c[m, n].
El programa es el siguiente:
#includelt; stdio.hgt;
#includelt; (char x [], char y[]);
int main()
{
char x[100], y[100];
int len;
while(1)
{
scanf("ss", x, y
);if(x[0]=='0') //Se acuerda que la primera cadena comience con '0' para indicar el final
break;
len =lcs_length(x, y );
printf("d\n", len
}
}
int); lcs_length(char x[] , char y[] )
{
int m, n, i, j, l[100][100];
m=strlen(x );
n=strlen(y);
for(i=0;ilt;m 1;i)
l [i][0] =0;
for(j=0;jlt;n 1;j)
l[0][j]=0;
for(i =1;ilt;=m;i )
for(j=1;jlt;=n;j )
if(x[i-1 ]==y[j -1]) //i, j comienzan desde 1, pero la cadena comienza desde 0
l[i][j]=l[i-1][j-1 ] 1;
p>else if(l[i][j-1]gt;l[i-1][j])
l[i][j] =l[i][j -1];
más
l[i][j]=l[i-1][j]; > return l[m][ n];
}
Dado que el cálculo de cada unidad de matriz toma Ο(1) tiempo, el algoritmo lcs_length toma Ο(mn).
Pensando: ¿Se puede ahorrar espacio?
2． Calcular el producto de matrices
En los cálculos científicos, muchas veces es necesario calcular el producto de matrices. La condición para multiplicar las matrices A y B es que el número de columnas de la matriz A sea igual al número de filas de la matriz B.
Si A es una matriz p×q y B es una matriz q×r, entonces su producto C=AB es una matriz p×r. A partir de esta fórmula, sabemos que calcular C=AB total *** requiere pqr tiempos de multiplicación. La fórmula de cálculo estándar es:
El problema actual es, dadas n matrices {A1, A2,..., An}. Entre ellos, Ai y Ai 1 son multiplicables, i = 1, 2,..., n-1. Se requiere calcular el producto continuo A1A2...An de estas n matrices.
Fórmula recursiva:
El programa es el siguiente:
#includelt; stdio.hgt;
int main()
p>{
int p[101], i, j, k, r, t, n
int m[101][101]; para seguir la explicación Mantenga la matriz consistente a partir de 1
int s[101][101] // Registre la posición de desconexión de la multiplicación de matrices i-ésima a j-ésima
scanf("d ",amp;n);
for(i=0;ilt;=n;i)
scanf("d",amp;p[ i]); // Lee el valor de p[i] (nota: 1 elemento de p[0] a p[n]***n)
for(i=1;ilt;= n;i) //Inicialización m[i][i]=0
m[i][i]=0
for(r=1; rlt; n; r ) //r es i , el valor de diferencia de j
for(i=1;ilt;n;i) //i es la fila
{
j=i r; // j es la columna
m[i][j]=m[i 1][j] p[i-1]*p[i]*p[j ]; //Dar m[i] [j]Asignar valor inicial
s[i][j]=i;
for(k=i 1;klt;j; k)
{
t=m[i][k] m[k 1][j] p[i-1]*p[k]*p[j] ;
if (tlt; m[i][j])
{
m[i][j]=t //M[i] ][j] toma el valor mínimo
s[i][j]=k;
}
}
}
printf("d ", m[1][n]);
}
3. Triangulación óptima de un polígono convexo
Un polígono es una curva cerrada lineal por partes en el plano. En otras palabras, un polígono se compone de una serie de segmentos de línea recta conectados de un extremo a otro. Los segmentos de recta que forman un polígono se llaman lados del polígono. Los puntos que conectan dos lados de un polígono se llaman vértices del polígono. Si no hay vértices comunes entre los lados de un polígono, excepto los vértices que los conectan, el polígono se llama polígono simple. Un polígono simple divide el plano en 3 partes: todos los puntos encerrados dentro del polígono forman el interior del polígono; el polígono mismo forma el límite del polígono y los puntos restantes en el plano forman el exterior del polígono. Cuando un polígono simple y su interior forman un conjunto convexo cerrado, el polígono simple se llama polígono convexo. Es decir, todos los puntos en el segmento de línea recta conectados por dos puntos cualesquiera en el límite o dentro del polígono convexo están dentro o en el límite del polígono convexo.
Por lo general, un polígono convexo está representado por una secuencia de vértices de polígono en sentido antihorario, es decir, P=lt; v0, v1,…, vn-1gt significa que tiene n lados v0v1, v1v2,…, vn- Un polígono convexo de 1vn, donde se acuerda v0=vn.
Si vi y vj son dos vértices no adyacentes en el polígono, el segmento de recta vivj se llama cuerda del polígono. Chord divide el polígono en dos subpolígonos convexos lt;vi,vi 1,…,vjgt;y lt;vj,vj 1,…,vigt;. La triangulación de un polígono es un conjunto T de cuerdas que divide el polígono en triángulos que no se superponen. La figura muestra dos triangulaciones diferentes de un polígono convexo.
El problema de triangulación óptima de polígonos convexos es: dado un polígono convexo P=lt; v0, v1,..., vn-1gt y definido sobre un triángulo compuesto por los lados y cuerdas del; polígono Función de peso ω. Se requiere determinar una triangulación del polígono convexo tal que el peso correspondiente a la triangulación, es decir, la suma de los pesos de los triángulos en la triangulación, sea mínimo.
En el triángulo se pueden definir varias funciones de peso W. Por ejemplo: defina ω(△vivjvk)=|vivj| |vivk|vkvj|, donde |vivj| es la distancia euclidiana del punto vi a vj. La triangulación óptima correspondiente a esta función de peso es la triangulación de longitud mínima de cuerda. (Nota: el algoritmo para resolver este problema debe ser aplicable a cualquier función de peso)
4. Misil de defensa
Un nuevo tipo de misil de defensa puede interceptar múltiples misiles atacantes. Puede volar hacia adelante o hacia abajo a velocidades muy altas y puede interceptar misiles atacantes sin sufrir daños, pero no puede volar hacia atrás ni hacia arriba. Pero hay un inconveniente. Aunque puede alcanzar cualquier altitud cuando se lanza, sólo puede interceptar misiles que estén a menor o a la misma altitud que la última vez que interceptó el misil. Este nuevo tipo de misil de defensa se está probando actualmente. En cada prueba, se lanzan una serie de misiles de prueba (estos misiles se lanzan en un intervalo fijo y vuelan a la misma velocidad. La información que el misil de defensa puede obtener incluye la altura). de cada misil atacante y el orden en que se lanzan. Ahora debemos compilar un programa para encontrar el número máximo de misiles ofensivos que el misil defensivo puede interceptar en cada prueba. Un misil que puede ser interceptado debe cumplir una de las dos condiciones siguientes:
a) Es el primer misil interceptado por un misil defensivo en esta prueba;
b) Fue un misil lanzado después del lanzamiento del último misil interceptado, y su altura no fue mayor que la altura del último misil interceptado.
Datos de entrada: la primera línea es un número entero n, y cada n subsiguiente tiene un número entero que representa la altura del misil.
Datos de salida: Número máximo de misiles interceptores.
Análisis: Defina l[i] como la opción para interceptar el i-ésimo misil y el número máximo de misiles que se pueden interceptar a partir de este misil.
Dado que se selecciona el i-ésimo misil, la altura del siguiente misil j a ser interceptado debe ser menor o igual a su altura, por lo que l[i] debe ser igual a cada j de i+ 1 a n, satisfaciendo h [j]lt = el valor máximo de l[j] en j de h[i].
El programa es el siguiente:
#includelt; stdio.hgt
int main()
{
int i, j, n, max, h[100], l[100]
scanf("d", amp; n);
for(i) =0; ilt; n; i )
scanf("d", y h[i]);
for(i=n-2;igt;=0;i--)
{
max=0;
for(j= i 1; jlt; n; j )
si(h[i]gt; h[j]amp; amp; maxlt; l[j])
max=l[ j];
l[i]=máx 1;
}
printf("d", l[0]); p>}
5. Fusionar piedras
Hay n montones de piedras (nlt; = 100) colocadas alrededor de un patio de juegos circular. Ahora es necesario fusionar las piedras en un montón en orden. Se estipula que solo se pueden seleccionar dos pilas adyacentes para fusionarlas en una nueva pila cada vez, y el número de piedras en la nueva pila se registrará como la puntuación de la fusión. Escriba un programa para leer el número de pila n y el número de piedras en cada pila (lt; = 20) del archivo.
Elija un plan para fusionar piedras de modo que después de n-1 fusiones, la puntuación total sea la más pequeña;
Datos de entrada:
La primera fila es una montón de piedras Count n;
La segunda línea es el número de piedras en cada montón, separadas por un espacio entre cada dos números.
Datos de salida:
El plan de fusión con la puntuación más pequeña desde la primera hasta la enésima fila. La línea n 1 es una línea en blanco. Desde la línea n 2 hasta la línea 2 n 1 es la solución de fusión con la puntuación máxima. Cada plan de fusión está representado por n líneas, donde la i-ésima línea (1lt; =ilt; =n) representa el número de piedras en cada pila antes de la i-ésima fusión (salida en el sentido de las agujas del reloj, la pila que salga primero) . Se requiere expresar el número de los dos montones de piedras que se fusionarán como números negativos correspondientes.
Entrada de muestra
4
4 5 9 4
Salida de muestra
-4 5 9 -4
-8 -5 9
-13 -9
22 4 -5 -9 4
4 -14 -4
-4-18
22
6. Árbol padre de costo mínimo
Hay una fila de números, ***n, por ejemplo: 22 14 7 13 26 15 11. Se pueden fusionar dos números adyacentes cualesquiera. El costo de la fusión es la suma de los dos números. Después de una fusión continua, finalmente se clasifican en una pila. La suma de todos los costos de la fusión se denomina costo total. , de modo que se minimice el coste total.
Los formatos de datos de entrada y salida son los mismos que los de "Stone Merge".
Entrada de muestra
4
12 5 16 4
Salida de muestra
－12 -5 16 4
17 -16 -4
-17 -20
37
7． Compras en tienda
Cada artículo en una tienda tiene un precio. Por ejemplo, el precio de una flor es 2 UCI (la unidad monetaria del concurso de informática es 5 UCI); Para atraer a más clientes, la tienda ofrece precios de descuento especiales. Los productos de oferta especial son uno o más productos agrupados en un grupo. Y vender a precio reducido.
Por ejemplo: el precio de 3 flores no es 6 sino 5 UCI; el precio de 2 jarrones más 1 flor es 10 UCI en lugar de 12 UCI.
Escribir un programa para calcular el coste de los bienes adquiridos por un cliente. Aproveche los precios con descuento para minimizar los pagos de los clientes. Tenga en cuenta que no puede cambiar el tipo y la cantidad de productos comprados por los clientes. Incluso si agregar algunos productos reducirá el pago total, no puede realizar ningún cambio. Supongamos que los precios de varios productos tienen descuentos como se describe anteriormente, y un cliente compra los siguientes artículos: 3 flores y 2 jarrones. Entonces el cliente a pagar es 14 UCI porque:
1 flor más 2 jarrones precio de descuento: 10 UCI
2 flores precio regular: 4 UCI
Datos de entrada: el primer archivo ENTRADA. El TXT describe los artículos comprados por el cliente (colocados en la cesta de la compra); el segundo archivo describe los artículos con descuento y los precios proporcionados por la tienda (el nombre del archivo es OFF ER. TXT). En ambos archivos sólo se utilizan números enteros.
El primer archivo INPUT. El formato de TXT es: la primera línea es un número B (0≤B≤5), que indica la cantidad de tipos de bienes comprados. La siguiente fila ***B contiene 3 números C, K y P en cada fila. C representa el código del producto (cada producto tiene un código único), 1≤C≤999. K representa el número total de compras de este producto, 1≤K≤5. P es el precio unitario normal de este producto (el precio de cada producto), 1≤P≤999. Tenga en cuenta que se pueden colocar un máximo de 5*5=25 artículos en la cesta de la compra.
El segundo archivo OFERTA. El formato de TXT es: la primera línea es un número S (0≤S≤9 9), lo que significa ***hay S tipos de descuentos. Hay ***S líneas a continuación. Cada línea describe el tipo de producto en una combinación de productos preferenciales. A continuación se muestran varios pares de números (C, K), donde C representa el código del producto, 1≤C≤999. K representa la cantidad de este bien en esta combinación, 1≤K≤5. El último número P en este banco (1≤ P≤9999) representa el precio preferencial de esta combinación de productos. Por supuesto, el precio con descuento es inferior a la suma de los precios habituales de los artículos del paquete.
Datos de salida: en el archivo de salida OUTPUT. Escriba un número (una línea) en el TXT, que represente el pago mínimo a pagar por el cliente por el producto comprado (el archivo de entrada especifica el producto comprado).
8. Presupuesto de viaje
Una agencia de viajes necesita estimar el coste mínimo de viajar en coche de una ciudad a otra. Hay varias gasolineras a lo largo de la carretera y los cargos en cada gasolinera no son necesariamente los mismos. El presupuesto de viaje tiene las siguientes reglas:
Si el tanque de combustible está lleno a más de la mitad, no se detenga a repostar a menos que el combustible en el tanque no pueda soportar la siguiente parada cada vez que reposte; repostar combustible en una gasolinera, el conductor tiene que gastar 2 yuanes para comprar comida; el conductor no tiene que preparar gasolina extra para otras situaciones inesperadas, el coche llena el depósito de gasolina en el punto de partida al salir; al grano (1 yuan = 100 puntos). Escriba un programa para estimar el costo mínimo de conducir una ruta determinada.
Datos de entrada: lee datos del archivo de texto "route.dat" en el directorio actual. Introduzca varias rutas de viaje en el siguiente formato:
La primera línea es la distancia desde el punto inicial hasta el punto final (número real)
La segunda línea son tres números reales, seguidos por un número entero, cada dos datos separados por un espacio. El primer número es la capacidad del tanque de combustible del automóvil (litros), el segundo número son los kilómetros recorridos por litro de gasolina, el tercer número es el costo de llenar el tanque en el punto de partida y el cuarto número es el número de gasolineras. (<=50). Cada línea posterior incluye dos números reales, separados por un espacio entre cada dato. El primer número es la distancia de la gasolinera desde el punto de partida y el segundo número es el precio por litro de gasolina en la gasolinera (yuanes/ascensor). ). Las gasolineras están dispuestas en orden ascendente según su distancia desde el punto de partida. Todos los insumos deben tener soluciones.
Datos de salida: las respuestas se envían al archivo de texto "route.out" en el directorio actual. El archivo consta de dos líneas. La primera línea es un número real y un número entero. El número real es el coste mínimo del viaje, en yuanes, con precisión de minutos. El número entero representa el número N de gasolineras a lo largo del camino. La segunda línea son N números enteros, que representan el número de N gasolineras, ordenados en orden ascendente.
Los datos están separados por un espacio y no hay espacios adicionales.
Entrada de muestra
516,3 38,09 1
15,7 22,1 20,87 3 2
125,4 1,259
297,9 1,129
345,2 0,999
Resultado de muestra
38,09 1
2
9. Guardia de Palacio
Después del incidente que involucró al príncipe Taiping, Lu Xiaofeng se convirtió en el guardaespaldas de primera clase especialmente contratado por el emperador. El palacio comienza en la Puerta Meridiana y termina en los dormitorios de las concubinas en el harén. Tiene forma de árbol. Algunos palacios se pueden ver entre sí. El palacio está fuertemente vigilado, con un puesto cada tres escalones y un centinela cada cinco escalones. Cada palacio debe estar vigilado las 24 horas del día. El costo de organizar guardias en diferentes palacios. Sin embargo, los fondos de Lu Xiaofeng eran insuficientes y, de todos modos, no podía colocar guardias amas de casa en todos los palacios.
Programe y calcule para ayudar a Lu Xiaofeng a organizar los guardias, de modo que el dinero gastado pueda minimizarse mientras protege todo el palacio.
Datos de entrada: Los datos de entrada los proporciona un archivo de texto llamado intput.txt. Los datos en el archivo de entrada representan un árbol, que se describe a continuación:
En la línea 1, n representa el número de nodos en el árbol.
De la línea 2 a la línea n 1, cada línea describe la información de cada nodo del palacio, en orden: la etiqueta del nodo del palacio i (0lt; ilt; = n), y la estación de guardia se coloca en el palacio Los fondos requeridos k, el número de hijos del borde m y los siguientes m números son las etiquetas r1, r2,..., rm de los m hijos de este nodo.
Para un árbol con n (0 lt; n lt; = 1500) nodos, las etiquetas de los nodos están entre 1 yn, y las etiquetas no se repiten.
Datos de salida: salida al archivo output.txt. El archivo de salida contiene solo un número, la cantidad mínima solicitada.
Datos de entrada de muestra como se muestran a la derecha:
Entrada de muestra
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
Salida de muestra
25
10． Problema con la sala de juegos
Hay varias salas de juegos dentro de una sala de juegos, y dentro de cada sala de juegos hay varias salas de juegos, dentro de cada sala de juegos hay salas de juegos, etc. Puedes obtener una cierta cantidad de felicidad ingresando a cada sala de juegos. El precio del boleto de cada sala de juegos es mayor o igual a 0 y tiene un valor de felicidad. Solo cuando ingresas a una sala de juegos puedes ingresar a la sala de juegos dentro de ella. Xiao Ming ahora tiene For n yuanes, pregunta cuánta felicidad puedes obtener como máximo.
11. *Problema genético
Existen dos secuencias genéticas conocidas como s: AGTAGT; t: ATTAG. Ahora desea agregar algunos espacios a la secuencia, primero iguale las longitudes de las dos secuencias y, segundo, haga coincidir los símbolos correspondientes de las dos cadenas para obtener el valor máximo. Solo hay cuatro tipos de genes, representados por A, G, C y T respectivamente. No se permite que dos espacios correspondan en la coincidencia. El valor coincidente de dos símbolos cualesquiera se proporciona en la siguiente tabla:
A G C T ]
A 5 -2 -1 -2 -4
G -2 5 -4 -3 -2
C -1 -4 5 -5 -1
T -2 -3 -5 5 -2
] -4 -2 -1 -2
Sugerencia: Defina el problema l[i][j] toma los primeros i elementos de la primera secuencia y los primeros j elementos de la segunda secuencia, el valor máximo de estas dos secuencias más espacios. Su valor óptimo está relacionado con tres subproblemas, l[i-1][j-1], l[i][j-1], l[i-1][j].
La fórmula recursiva se establece de la siguiente manera:
donde m[0][t[j] representa el valor correspondiente que coincide con el espacio en la tabla y t[j].
Pensando: Inicialización de este problema.
12. *Carreras de caballos Tian Ji
Carreras de caballos Tian Ji y Qi Wang, cada bando tiene n caballos participando (nlt;=100), la apuesta por cada juego es 1 tael de oro, ahora se sabe que cada caballo de velocidad Qi King y Tian Ji, y el rey Qi debe jugar de acuerdo con la velocidad del caballo de rápido a lento. Ahora quiero que escribas un programa para ayudar a Tian Ji a calcular cuántos taels de oro es su mejor resultado para ganar. (la pérdida está representada por un número negativo).
Análisis: Primero ordene, coloque la velocidad del caballo del rey Qi en la matriz a y coloque la velocidad del caballo de Tian Ji en la matriz b. El algoritmo aplicado a este problema es una combinación de programación dinámica y algoritmo codicioso. Comience con el caballo más débil de los dos:
Si el caballo de Tian Ji es rápido, deje que los dos caballos corran;
Si el caballo de Tian Ji es lento, déjelo lidiar con ambos caballos. El caballo más rápido del rey;
Si la velocidad de los dos caballos es igual, hay dos opciones en este momento, o compiten o pueden enfrentarse al caballo más rápido del rey de Qi.
Defina el subproblema: l(i, j) es el beneficio máximo que Tian Ji obtiene cuando los caballos j del rey Qi a partir del i-ésimo caballo compiten con los caballos j más rápidos de Tian Ji.
Regla:
Durante la implementación específica del programa, para adaptarse a que los datos c comienzan desde 0, con ligeros cambios, se define el subproblema: l (i, j) es el rey Qi que comienza desde i. El caballo comienza a correr con el i+jésimo caballo ***j1 y el caballo j1 más rápido de Tian Ji, y Tian Ji obtiene el máximo beneficio. Durante la inicialización: l[i][0] representa el resultado de la carrera entre el i-ésimo caballo del rey Qi y el caballo más rápido de Tian Ji.
El programa es el siguiente:
#includelt; stdio.hgt;
void readdata();
void init() ;
void init();
p>
int n, a[100], b[100], l[100][100];
int main()
{
int i, j;
readdata()
init(); /p>
for(i=n-2; igt; =0; i --)
for(j=1;jlt;n-i;j)
si (a[i j]lt;b[j])
l [i][j]=l[i][j-1] 1;
else if(a[ i j]gt;b[j])
l[i] [j]=l[i 1][j-1]-1
else if(l[i; 1][j-1]-1gt; l[i][j-1])
l[i][j]=l[i 1][j-1]-1
else
l[i][j] =l[i][j-1];
printf("d",l[0][n -1]);
}
void readdata()
{
int i
scanf; ("d", y n);
for(i =0;ilt;n;i)
scanf("d",y;a[i]);
for(i=0;ilt;n;i)
scanf("d",amp;b[i]);
}
void init()
{
int i;
// qsort(a, n); // omitido
for(i=0; ilt; n; i)
{
if(a[i]lt; b[0])
l[i][0]=1;
si( a[i]==b[0])
l[i][0]=0; p>
más
l[i][0] =-1;
}
}