Descargo de responsabilidad: el método que se describe a continuación no es universal, pero a menudo puede resolver un problema o ayudarlo a encontrar la solución correcta.
Si el problema se reduce al hecho de que es necesario dividir la matriz en subsegmentos que no se intersecan (una secuencia de elementos consecutivos) de manera óptima (o contar el número de divisiones adecuadas), entonces vale la pena intentar resolverlo. usando programación dinámica.
Un esquema de solución de ejemplo es el siguiente:
dp[i] - respuesta para los primeros elementos i
Contando dp[i]: como solo estamos considerando los primeros i elementos, el i-ésimo elemento será el último, lo que significa que este elemento estará en el último subsegmento y, al mismo tiempo, el más a la derecha allí. Por lo tanto, podemos iterar sobre el límite izquierdo del último subsegmento j. En el proceso de enumeración, calcularemos el valor de este subsegmento y, si es correcto, volveremos a calcular dp[i] hasta dp[j - 1] y el valor del subsegmento [j;i].
Considere el siguiente problema simple: dada una matriz de enteros, debe dividirla en la cantidad mínima de subsegmentos que no se intersecan para que cada número se incluya en algún subsegmento y que cada subsegmento contenga los mismos números. Por ejemplo, para una matriz 1 2 2 3 3 3 2 1 1, la partición óptima se ve así: [1] [2 2] [3 3 3] [2] [1 1]. Esta tarea se resuelve fácilmente simplemente pasando por la matriz (ponemos todos los mismos elementos consecutivos en un subsegmento), pero lo resolveremos usando programación dinámica como ejemplo.
interno;
cin>> norte;
// llenar matriz con índice 1
vectorarr(n + 1);
para (int i = 1; i <= n; i++)
cin>> arri[yo];
// establecer inicialmente +oo en valores dp
vector dp(n + 1, 1000000000);
// una matriz de longitud cero no necesita dividirse, por lo que la respuesta es 0
pd[0] = 0;
// cuenta la respuesta para dp[i] en i ascendente
para (int i = 1; i <= n; i++) {
// actualmente arr[i] es el último elemento, por lo que será el número más a la derecha en el último subsegmento
// recorrer todas las opciones para saber dónde comenzó este último subsegmento
para (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// si encuentra un elemento que no es igual al último, entonces el subsegmento contendrá números diferentes, y esto no cumple la condición
// no tiene sentido continuar, porque desplazando el borde izquierdo a la izquierda, este elemento no desaparecerá, por lo que rompemos
romper;
}
// imagina que el último subsegmento fue [j;i]
// por lo que debe tomar la partición óptima de los primeros elementos j-1 y agregar 1 (el subsegmento [j; i] en sí)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Si los elementos pueden no pertenecer a ninguno de los subsegmentos, solo debe considerar la opción adecuada, como dp[i] = dp[i - 1]
|
Si es necesario dividir la matriz en exactamente k subsegmentos, simplemente se agrega el segundo parámetro en la programación dinámica: en cuántos segmentos dividir.
Es decir, ahora consideraremos el siguiente dp:
dp[i][j] es la respuesta para los primeros i elementos, si los dividimos exactamente en j segmentos.
Tenga cuidado con los estados no válidos.
El recálculo de la dinámica es el mismo, pero teniendo en cuenta el segundo parámetro. Es decir, contando dp[i][k] y clasificando a través del borde izquierdo del último subsegmento j, volvemos a calcular dp[i][k] hasta dp[j - 1][k - 1] y el valor del segmento [Ji].
|
Descargo de responsabilidad: el método que se describe a continuación no es universal, pero a menudo puede resolver un problema o ayudarlo a encontrar la solución correcta.
Si hay un conjunto de brechas ubicadas en algún eje (generalmente el eje del tiempo o índices de alguna matriz) y necesita elegir algunas de ellas de manera óptima para que las brechas seleccionadas no se crucen, entonces debe intentar usar programación dinámica .
Esquema de solución aproximado:
Inicialmente, ordenamos los espacios disponibles por el borde derecho. Comencemos con la siguiente dinámica: dp[i] - la respuesta para los primeros intervalos i.
Recalcularemos de la siguiente manera: primero, considere la situación de que este intervalo no se usará, luego solo dp[i] = dp[i-1]. Tenga en cuenta que esto asegura que los valores de dp[i] no disminuyan a medida que i crece. Y esto es lógico, porque. agregando una nueva brecha, no podemos empeorar la respuesta global: o simplemente ignoramos la nueva brecha, o construimos una variante más rentable usándola. Ahora, si queremos usar el espacio i-ésimo, entonces podemos usar esos espacios cuyos bordes derechos son menores que el borde izquierdo del espacio actual, ya que debemos elegir un conjunto de espacios que no se superpongan. Para hacer esto, inicialmente clasificamos los espacios por el borde derecho, de modo que ahora podamos encontrar de manera eficiente la posición requerida. Esto se puede hacer analíticamente, si es posible, pero en el caso general es posible encontrar una brecha con un binsearch, cuyo borde derecho es menor que el borde izquierdo del actual y, al mismo tiempo, el máximo posible. uno. Queremos maximizar el borde derecho por razones codiciosas, porque a medida que crece, la respuesta solo puede aumentar. En consecuencia, encontramos la posición p requerida y recalculamos dp[i] a través de dp[p] y el i-ésimo intervalo.
|