Este documento explora la aplicación de técnicas avanzadas de programación dinámica para resolver problemas de optimización, centrándose principalmente en la optimización de pendiente (Convex Hull Trick) y una breve mención de la descomposición en raíz cuadrada (Square Root Decomposition).
P3628 \[APIO2010\] Equipo de Acción Especial
El problema del Equipo de Acción Especial es un ejemplo clásico donde la optimización de pendiente puede aplicarse para reducir la complejidad temporal de una solución de programación dinámica. La formulación genarel de una recurrencia DP susceptible a esta optimización es de la forma:
dp[i] = min/max (dp[j] + C(i, j))
donde C(i, j) es una función cuadrática o lineal con respecto a i y j. Para este problema, la expresión de la función de costo se puede manipular algebraicamente para obtener la forma Y = kX + B, donde k depende de i y X, Y, B dependen de j. El objetivo es mantener una envolvente convexa (superior o inferior) de puntos (X, Y) tal que se pueda consultar eficientemente el punto que minimiza o maximiza la expresión para un k dado.
Una regla general es que, si la pendiente k es monótona (siempre creciente o decreciente), se puede usar una cola monótona para mantener la envolvente convexa y realizar consultas en tiempo amortizado O(1). Si la consulta involucra minimizar Y - kX (o maximizar Y - kX), se requiere mantener una envolvente inferior (o superior).
Específicamente, si se busca \\(\\frac{Y_1 - Y_2}{X_1 - X_2} \\ge k\\), se mantiene una envolvente superior. Si se busca \\(\\frac{Y_1 - Y_2}{X_1 - X_2} \\leq k\\), se mantiene una envolvente inferior.
Al simplificar la expresión de DP, es crucial identificar los términos puros constantes, las variables puras y los coeficientes que multiplican las variables, los cuales formarán la pendiente k.
#include <iostream>
#include <vector>
#include <utility> // Para std::pair
#include <algorithm> // Para std::min/max
typedef long long tipoLargo;
// Estructura para gestionar la cola monótona (envolvente convexa)
class EnvolventeConvexa {
public:
std::vector<std::pair<tipoLargo, tipoLargo>> puntos;
std::vector<int> indicesOriginales; // Guarda el índice 'j' asociado al punto
int inicio, fin;
EnvolventeConvexa() : inicio(0), fin(-1) {}
// Calcula la pendiente entre dos puntos
double obtenerPendiente(const std::pair<tipoLargo, tipoLargo>& p1, const std::pair<tipoLargo, tipoLargo>& p2) {
if (p2.first == p1.first) { // Evitar división por cero
return (p2.second > p1.second) ? 1e18 : -1e18; // Infinito o menos infinito
}
return static_cast<double>(p2.second - p1.second) / (p2.first - p1.first);
}
// Comprueba si tres puntos forman un giro a la derecha (para envolvente inferior)
// O si el punto 'c' hace que la pendiente (a,c) sea menor o igual que (b,c) para quitar 'b'
bool esGiroDerecha(const std::pair<tipoLargo, tipoLargo>& pA, const std::pair<tipoLargo, tipoLargo>& pB, const std::pair<tipoLargo, tipoLargo>& pC) {
// (pB.y - pA.y) * (pC.x - pB.x) <= (pC.y - pB.y) * (pB.x - pA.x)
// Para envolvente superior, necesitamos el operador >=
// Aquí necesitamos <= para una envolvente superior (para quitar puntos que hacen que la curva se "doble hacia abajo")
return obtenerPendiente(pA, pB) <= obtenerPendiente(pB, pC);
}
// Elimina puntos ineficientes del frente de la cola
void consultar(double k_pendiente) {
while (inicio + 1 <= fin && k_pendiente < obtenerPendiente(puntos[inicio], puntos[inicio + 1])) {
inicio++;
}
}
// Agrega un nuevo punto a la cola, manteniendo la convexidad
void insertar(tipoLargo coord_x, tipoLargo coord_y, int original_idx) {
std::pair<tipoLargo, tipoLargo> nuevoPunto = {coord_x, coord_y};
while (inicio + 1 <= fin && esGiroDerecha(puntos[fin - 1], puntos[fin], nuevoPunto)) {
fin--;
}
fin++;
if (fin >= puntos.size()) {
puntos.push_back(nuevoPunto);
indicesOriginales.push_back(original_idx);
} else {
puntos[fin] = nuevoPunto;
indicesOriginales[fin] = original_idx;
}
}
// Retorna el punto óptimo actual
std::pair<tipoLargo, tipoLargo> obtenerFrentePunto() {
return puntos[inicio];
}
// Retorna el índice original asociado al punto óptimo
int obtenerFrenteIndice() {
return indicesOriginales[inicio];
}
};
tipoLargo calcularValorFuncion(tipoLargo val, tipoLargo coefA, tipoLargo coefB, tipoLargo coefC) {
return coefA * val * val + coefB * val + coefC;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numElementos;
tipoLargo coefA, coefB, coefC;
std::cin >> numElementos;
std::cin >> coefA >> coefB >> coefC;
std::vector<tipoLargo> valoresEntrada(numElementos + 1);
std::vector<tipoLargo> sumasPrefijo(numElementos + 1, 0);
std::vector<tipoLargo> resultadosDP(numElementos + 1, 0);
for (int i = 1; i <= numElementos; ++i) {
std::cin >> valoresEntrada[i];
sumasPrefijo[i] = sumasPrefijo[i - 1] + valoresEntrada[i];
}
EnvolventeConvexa gestorConvexa;
gestorConvexa.insertar(0, 0, 0); // (X_j, Y_j) para j=0
for (int i = 1; i <= numElementos; ++i) {
// La pendiente 'k' depende de 'i'
double pendienteK = 2.0 * coefA * sumasPrefijo[i];
gestorConvexa.consultar(pendienteK);
// Obtener el punto óptimo (sum_j, dp_j + a*sum_j^2 - b*sum_j)
std::pair<tipoLargo, tipoLargo> puntoOptimo = gestorConvexa.obtenerFrentePunto();
int idxOptimo = gestorConvexa.obtenerFrenteIndice();
// Calcular dp[i] usando el punto óptimo
// dp[i] = dp[j] + a*(sum[i]-sum[j])^2 + b*(sum[i]-sum[j]) + c
// dp[i] = (dp_j + a*sum_j^2 - b*sum_j) - 2*a*sum_i*sum_j + a*sum_i^2 + b*sum_i + c
// dp[i] = Y_j - k*X_j + a*sum_i^2 + b*sum_i + c
resultadosDP[i] = puntoOptimo.second - (tipoLargo)(pendienteK * puntoOptimo.first) + coefA * sumasPrefijo[i] * sumasPrefijo[i] + coefB * sumasPrefijo[i] + coefC;
// Insertar el nuevo punto (X_i, Y_i) en la envolvente
// X_i = sum_i
// Y_i = dp[i] + a*sum_i^2 - b*sum_i
gestorConvexa.insertar(sumasPrefijo[i], resultadosDP[i] + coefA * sumasPrefijo[i] * sumasPrefijo[i] - coefB * sumasPrefijo[i], i);
}
std::cout <>> resultadosDP[numElementos] << '\n';
return 0;
}
Problema "Dazzling" de Concurso Regional (Ejemplo de Raíz Cuadrada)
El problema "Dazzling" es un ejemplo que ilustra la técnica de descomposición en raíz cuadrada (también conocida como "root decomposition" o "sqrt decomposition"). Esta técnica se utiliza típicamente para optimizar algoritmos en problemas donde las consultas o actualizaciones tienen diferentes comportamientos según el tamaño de los datos involucrados. La idea principal es dividir el conjunto de datos en bloques de tamaño \\(\\sqrt{N}\\) para balancear la complejidad de las operaciones.
Generalmente, los elementos "pequeños" (por debajo de un umbral, a menudo \\(\\sqrt{N}\\)) se manejan con una lógica de DP o conteo más directa, mientras que los elementos "grandes" (por encima del umbral) se procesan con una estrategia diferente, que podría involucrar otra forma de DP o una estructura de datos más eficiente.
La complejidad de la solución se balancea de modo que tanto las operaciones para elementos pequeños como grandes tengan una complejidad similar, a menudo resultando en una complejidad total de \\(O(N\sqrt{N})\\) o \\(O((N+Q)\sqrt{N})\\) para consultas.
#include <iostream>
#include <vector>
#include <cstring> // Para memset
typedef long long tipoLargo;
const tipoLargo MODULO_OPERACION = 998244353;
const int UMBRAL_BLOQUES = 650; // Umbral para la descomposición en bloques
const int LIMITE_VALOR_S = 1023; // Límite para el primer DP
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
tipoLargo N_total, W_factor;
std::cin >> N_total >> W_factor;
if (N_total == 1) {
std::cout << 0 << '\n';
return 0;
}
// dpPequeño[i & S][j] almacena el resultado para 'i' elementos y el "peso" 'j'
// El & S se usa para la optimización de memoria (como un arreglo circular)
std::vector<std::vector<int>> dpPequeño(LIMITE_VALOR_S + 1, std::vector<int>(1400, 0));
// Primera fase de DP para 'j' pequeños (hasta UMBRAL_BLOQUES)
// El problema original parece involucrar el "peso" del último elemento añadido o similar.
// Asumimos que j representa un "peso" o una "condición" que no excede un cierto límite.
for (int i = 1; i <= N_total; ++i) {
std::fill(dpPequeño[i & LIMITE_VALOR_S].begin(), dpPequeño[i & LIMITE_VALOR_S].end(), 0);
if (i <= UMBRAL_BLOQUES) {
dpPequeño[i & LIMITE_VALOR_S][i] = 1; // Condición inicial
}
for (int j = 1; j <= 1000 && j <= i; ++j) {
tipoLargo val1 = (i - j >= 0 && j + 1 < 1400) ? (tipoLargo)W_factor * dpPequeño[(i - j) & LIMITE_VALOR_S][j + 1] : 0;
tipoLargo val2 = (i - j >= 0 && j - 1 >= 0) ? dpPequeño[(i - j) & LIMITE_VALOR_S][j - 1] : 0;
dpPequeño[i & LIMITE_VALOR_S][j] = (dpPequeño[i & LIMITE_VALOR_S][j] + val1 + val2) % MODULO_OPERACION;
}
}
tipoLargo respuestaFinal = 0;
for (int i = 1; i <= 1000; ++i) {
respuestaFinal = (respuestaFinal + dpPequeño[N_total & LIMITE_VALOR_S][i]) % MODULO_OPERACION;
}
// Segunda fase de DP para 'j' grandes (usando descomposición en raíz cuadrada)
// dpSubProblemaGrande[alternador][j]
// Aquí 'j' puede representar un valor que puede ir hasta 2*N_total
std::vector<std::vector<int>> dpSubProblemaGrande(2, std::vector<int>(2 * N_total + 1, 0));
dpSubProblemaGrande[0][N_total] = 1; // Condición inicial
bool alternador = 1;
for (int i = 1; i * UMBRAL_BLOQUES <= 2 * N_total; ++i) {
std::fill(dpSubProblemaGrande[alternador].begin(), dpSubProblemaGrande[alternador].end(), 0);
for (int j = 0; j <= 2 * N_total; ++j) {
tipoLargo term1 = (j + i <= 2 * N_total) ? (tipoLargo)W_factor * dpSubProblemaGrande[alternador ^ 1][j + i] : 0;
tipoLargo term2 = (j - i >= 0) ? dpSubProblemaGrande[alternador ^ 1][j - i] : 0;
dpSubProblemaGrande[alternador][j] = (dpSubProblemaGrande[alternador][j] + term1 + term2) % MODULO_OPERACION;
}
// Sumar resultados de la fase de bloques
for (int j = UMBRAL_BLOQUES + 1; j <= N_total; ++j) {
if ((tipoLargo)i * j <= 2 * N_total) {
respuestaFinal = (respuestaFinal + dpSubProblemaGrande[alternador ^ 1][2 * N_total - i * j]) % MODULO_OPERACION;
}
}
alternador ^= 1; // Alternar entre 0 y 1 para usar memoria de manera eficiente
}
std::cout << respuestaFinal << '\n';
return 0;
}
P3195 \[HNOI2008\] Empaque de Juguetes
El problema del Empaque de Juguetes es otro ejemplo paradigmático de la optimización de pendiente. La formulación de la recurrencia DP se establece como:
\\(dp[i] = \min_{j=0}^{i-1} \{dp[j] + (\sum_{k=j+1}^i C_k + (i-j) - L)^2 \} \\)
donde \\(C_k\\) es la longitud del k-ésimo juguete, y \\(L\\) es la longitud máxima permitida para una caja. Si definimos \\(S_i = \sum_{k=1}^i C_k + i\\) como la suma de longitudes de juguetes más el número de espacios entre ellos (o una unidad por juguete), la expresión se simplifica. Agregando 1 a \\(L\\) para manejar \\((i - (j+1) + \text{pref}_i - \text{pref}_j - L)\\) de manera más limpia, la fórmula se convierte en:
\\(dp[i] = \min_{j=0}^{i-1} \{dp[j] + (S_i - S_j - L')^2 \} \\)
donde \\(L' = L+1\\). Expandiendo el término cuadrático y reagrupando, buscamos la forma \\(Y = kX + B\\). Definimos \\(X_j = S_j\\) y \\(Y_j = dp[j] + S_j^2\\). La pendiente k será \\(2(S_i - L')\\). La expresión a minimizar para \\(dp[i]\\) se puede reescribir como:
\\(dp[i] = (S_i - L')^2 + \min_{j=0}^{i-1} \{ dp[j] + S_j^2 - 2(S_i - L')S_j \} \\)
Por lo tanto, queremos encontrar el \\(j\\) que minimice \\(Y_j - kX_j\\), donde \\(k = 2(S_i - L')\\). Esto requiere mantener una envolvente inferior de puntos \\((X_j, Y_j)\\).
Si tenemos dos puntos \\(j_1 < j_2\\), y si preferimos \\(j_2\\) sobre \\(j_1\\) para una pendiente \\(k\\), entonces la pendiente entre \\(j_1\\) y \\(j_2\\) debe ser menor o igual que \\(k\\):
\\(\\frac{Y_{j_2} - Y_{j_1}}{X_{j_2} - X_{j_1}} \le k\\)
Esta condición nos permite usar una cola monótona para mantener los puntos que forman la envolvente inferior.
#include <iostream>
#include <vector>
#include <utility> // Para std::pair
#include <algorithm> // Para std::min
typedef long long tipoLargo;
// Clase para implementar la cola monótona para la envolvente inferior
class ColaMonotonaPendiente {
public:
std::vector<std::pair<tipoLargo, tipoLargo>> puntosConvexos;
int indiceFrente, indiceFinal;
ColaMonotonaPendiente() : indiceFrente(0), indiceFinal(-1) {}
// Calcula la pendiente entre dos puntos
double calcularPendiente(const std::pair<tipoLargo, tipoLargo>& p1, const std::pair<tipoLargo, tipoLargo>& p2) {
if (p2.first == p1.first) { // Evitar división por cero
return (p2.second > p1.second) ? 1e18 : -1e18;
}
return static_cast<double>(p2.second - p1.second) / (p2.first - p1.first);
}
// Comprueba si tres puntos forman un giro a la izquierda (para envolvente inferior)
// Esto significa que el punto 'c' hace que la envolvente convexa "se doble" hacia arriba
bool esInnecesario(const std::pair<tipoLargo, tipoLargo>& pA, const std::pair<tipoLargo, tipoLargo>& pB, const std::pair<tipoLargo, tipoLargo>& pC) {
// La condición para envolvente inferior es que la pendiente (B, C) sea mayor que (A, B)
// Si no es así, 'B' es innecesario.
return calcularPendiente(pA, pB) >= calcularPendiente(pB, pC);
}
// Elimina puntos del final que rompen la convexidad
void insertarPunto(tipoLargo x_val, tipoLargo y_val) {
std::pair<tipoLargo, tipoLargo> nuevoPunto = {x_val, y_val};
while (indiceFrente + 1 <= indiceFinal && esInnecesario(puntosConvexos[indiceFinal - 1], puntosConvexos[indiceFinal], nuevoPunto)) {
indiceFinal--;
}
indiceFinal++;
if (indiceFinal >= puntosConvexos.size()) {
puntosConvexos.push_back(nuevoPunto);
} else {
puntosConvexos[indiceFinal] = nuevoPunto;
}
}
// Elimina puntos del frente que ya no son óptimos para la pendiente actual 'k'
void consultarOptimo(double k_pendiente) {
while (indiceFrente + 1 <= indiceFinal && k_pendiente >= calcularPendiente(puntosConvexos[indiceFrente], puntosConvexos[indiceFrente + 1])) {
indiceFrente++;
}
}
// Retorna el punto óptimo actual en el frente de la cola
std::pair<tipoLargo, tipoLargo> obtenerFrente() {
return puntosConvexos[indiceFrente];
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numJuguetes;
tipoLargo longitudMaximaCaja;
std::cin >> numJuguetes >> longitudMaximaCaja;
// Ajuste de L para incluir el -1 en la fórmula (L')
longitudMaximaCaja++;
std::vector<tipoLargo> longitudesJuguetes(numJuguetes + 1);
std::vector<tipoLargo> sumasAjustadas(numJuguetes + 1, 0); // S_i = sum(C_k) + i
std::vector<tipoLargo> minCostosDP(numJuguetes + 1);
for (int i = 1; i <= numJuguetes; ++i) {
std::cin >> longitudesJuguetes[i];
sumasAjustadas[i] = sumasAjustadas[i - 1] + longitudesJuguetes[i];
}
// Calcular S_i = sum(C_k) + i
for (int i = 1; i <= numJuguetes; ++i) {
sumasAjustadas[i] += i;
}
ColaMonotonaPendiente gestorPendiente;
// Insertar el punto base (X_0, Y_0) donde X_0 = S_0 = 0 y Y_0 = dp[0] + S_0^2 = 0
gestorPendiente.insertarPunto(0, 0);
for (int i = 1; i <= numJuguetes; ++i) {
tipoLargo k_val = 2LL * (sumasAjustadas[i] - longitudMaximaCaja);
gestorPendiente.consultarOptimo(k_val);
std::pair<tipoLargo, tipoLargo> puntoOptimo = gestorPendiente.obtenerFrente();
// dp[i] = (S_i - L')^2 + Y_j - k*X_j
minCostosDP[i] = (sumasAjustadas[i] - longitudMaximaCaja) * (sumasAjustadas[i] - longitudMaximaCaja) + puntoOptimo.second - k_val * puntoOptimo.first;
// Insertar el nuevo punto (X_i, Y_i) = (S_i, dp[i] + S_i^2)
gestorPendiente.insertarPunto(sumasAjustadas[i], minCostosDP[i] + sumasAjustadas[i] * sumasAjustadas[i]);
}
std::cout << minCostosDP[numJuguetes] << '\n';
return 0;
}
P2120 \[ZJOI2007\] Construcción de Almacenes
El problema de la Construcción de Almacenes es conceptualmente similar a los problemas de optimización de pendiente anteriores. Involucra la selección de ubicaciones para almacenes para minimizar un costo total que incluye costos de construcción y costos de distribución. La formulación de la DP también se reduce a una forma \\(dp[i] = \min_{j<i} \{ dp[j] + \text{costo}(j, i) \}\\) que puede transformarse en \\(Y = kX + B\\).
Un detalle importante en este problema es el manejo de casos donde el peso \\(p_i\\) es cero, lo que puede implicar que el costo de construcción en esa ubicación específica no contribuye a la suma o que se pueda heredar el valor DP del estado anterior sin incurrir en costos adicionales de construcción. Al igual que en problemas anteriores, la clave es la manipulación algebraica para identificar la pendiente \\(k\\) y los puntos \\((X_j, Y_j)\\) que formarán la envolvente convexa. La elección entre envolvente superior o inferior depednerá de si se busca minimizar o maximizar la expresión \\(Y - kX\\) y de la monotonía de \\(k\\).
#include <iostream>
#include <vector>
#include <utility> // Para std::pair
#include <algorithm> // Para std::min
typedef long long tipoLargo;
const tipoLargo INF_GRANDE = 2e18; // Un valor lo suficientemente grande para representar infinito
// Clase para la gestión de la envolvente convexa (cola monótona)
class OptimizadorPendiente {
public:
std::vector<std::pair<tipoLargo, tipoLargo>> puntosCola;
int frenteIndice, finalIndice;
OptimizadorPendiente() : frenteIndice(0), finalIndice(-1) {}
// Calcula la pendiente entre dos puntos
double obtenerPendiente(const std::pair<tipoLargo, tipoLargo>& p1, const std::pair<tipoLargo, tipoLargo>& p2) {
if (p2.first == p1.first) {
return (p2.second > p1.second) ? 1e18 : -1e18; // Manejar pendientes verticales
}
return static_cast<double>(p2.second - p1.second) / (static_cast<double>(p2.first - p1.first));
}
// Comprueba si el punto intermedio (pB) es redundante para una envolvente inferior
// i.e., si la pendiente (pA, pB) es mayor o igual que la pendiente (pB, pC)
bool esRedundante(const std::pair<tipoLargo, tipoLargo>& pA, const std::pair<tipoLargo, tipoLargo>& pB, const std::pair<tipoLargo, tipoLargo>& pC) {
return obtenerPendiente(pA, pB) >= obtenerPendiente(pB, pC);
}
// Inserta un nuevo punto al final de la cola, manteniendo la envolvente inferior
void añadirPunto(tipoLargo x_coord, tipoLargo y_coord) {
std::pair<tipoLargo, tipoLargo> nuevoPunto = {x_coord, y_coord};
while (frenteIndice + 1 <= finalIndice && esRedundante(puntosCola[finalIndice - 1], puntosCola[finalIndice], nuevoPunto)) {
finalIndice--;
}
finalIndice++;
if (finalIndice >= puntosCola.size()) {
puntosCola.push_back(nuevoPunto);
} else {
puntosCola[finalIndice] = nuevoPunto;
}
}
// Remueve puntos del frente que ya no son óptimos para la pendiente 'k'
void limpiarFrente(double k_valor) {
while (frenteIndice + 1 <= finalIndice && k_valor >= obtenerPendiente(puntosCola[frenteIndice], puntosCola[frenteIndice + 1])) {
frenteIndice++;
}
}
// Retorna el punto actual en el frente de la cola (el óptimo para la pendiente actual)
std::pair<tipoLargo, tipoLargo> obtenerPuntoOptimo() {
return puntosCola[frenteIndice];
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numUbicaciones;
std::cin >> numUbicaciones;
std::vector<tipoLargo> ubicacionesX(numUbicaciones + 1);
std::vector<tipoLargo> pesosMercanciaP(numUbicaciones + 1);
std::vector<tipoLargo> costosConstruccionC(numUbicaciones + 1);
std::vector<tipoLargo> sumasPesosPrefijo(numUbicaciones + 1, 0); // P[i]
std::vector<tipoLargo> sumasCostosDistribucion(numUbicaciones + 2, 0); // Sum[P_k * X_k] de i+1 a N
std::vector<tipoLargo> resultadosDP(numUbicaciones + 1, INF_GRANDE);
for (int i = 1; i <= numUbicaciones; ++i) {
std::cin >> ubicacionesX[i] >> pesosMercanciaP[i] >> costosConstruccionC[i];
sumasPesosPrefijo[i] = sumasPesosPrefijo[i - 1] + pesosMercanciaP[i];
}
// Calcular sumas de costos de distribución inversas: Sum[P_k * X_k] para k de (i+1) a N
// Esta es una suma de prefijos reversa. sumasCostosDistribucion[i] = Sum_{k=i+1}^N (P_k * X_k)
// Se calcula para facilitar la expresión del costo.
for (int i = numUbicaciones - 1; i >= 0; --i) {
sumasCostosDistribucion[i] = sumasCostosDistribucion[i + 1] + (ubicacionesX[i + 1] * pesosMercanciaP[i + 1]);
}
resultadosDP[0] = 0; // Costo base para 0 ubicaciones
OptimizadorPendiente optPendiente;
// Insertar el punto inicial (X_j, Y_j) = (P[j], dp[j] + Sum_{k=j+1}^N (P_k * X_k))
optPendiente.añadirPunto(sumasPesosPrefijo[0], resultadosDP[0] + sumasCostosDistribucion[0]);
for (int i = 1; i <= numUbicaciones; ++i) {
// La pendiente k para este problema es X_i
tipoLargo valorPendienteK = ubicacionesX[i];
optPendiente.limpiarFrente(valorPendienteK); // Como k es creciente, quitamos del frente
std::pair<tipoLargo, tipoLargo> puntoOptimo = optPendiente.obtenerPuntoOptimo();
// La fórmula de DP se reduce a:
// dp[i] = dp[j] + (sum_P_j - sum_P_i) * X_i + (sum_{k=j+1}^i P_k * X_k) + C_i
// Después de manipulación y reorganización a Y - kX + B:
// dp[i] = Y_j - X_i*X_j + (Sum_{k=i+1}^N P_k X_k) - (Sum_{k=j+1}^N P_k X_k) + X_i*P_i + C_i
// dp[i] = Y_j - X_i*X_j + (sumasCostosDistribucion[i]) - (sumasCostosDistribucion[j]) + X_i*P_i + C_i
// Pero Y_j = dp[j] + sumasCostosDistribucion[j]. Reorganizando:
// dp[i] = (dp[j] + sumasCostosDistribucion[j]) - X_i*P[j] + sumasCostosDistribucion[i] - X_i*P[i] + C_i
// dp[i] = Y_j - k*X_j + sumasCostosDistribucion[i] - X_i*sumasPesosPrefijo[i] + C_i
resultadosDP[i] = puntoOptimo.second - valorPendienteK * puntoOptimo.first + sumasCostosDistribucion[i] - valorPendienteK * sumasPesosPrefijo[i] + costosConstruccionC[i];
// Considerar el caso especial donde p[i]=0. En este caso, el almacén no sirve a nadie
// y podemos simplemente heredar el costo mínimo de la etapa anterior si es mejor.
// Esto depende de la definición exacta del problema, si un p[i]=0 puede tener un almacén.
// Si es que no se puede construir un almacén en un p[i]=0, o si se puede pero no tiene efecto en distribucion
// la formula general debería manejarlo, o dp[i] = min(dp[i], dp[i-1]).
// Suponiendo que la DP ya maneja esto o que es una condición externa:
// if (pesosMercanciaP[i] == 0) {
// resultadosDP[i] = std::min(resultadosDP[i], resultadosDP[i-1]);
// }
// Insertar el nuevo punto (P[i], dp[i] + sumasCostosDistribucion[i])
optPendiente.añadirPunto(sumasPesosPrefijo[i], resultadosDP[i] + sumasCostosDistribucion[i]);
}
std::cout << resultadosDP[numUbicaciones] << '\n';
return 0;
}