Batch Scheduling

Análisis oficial 

Explicación

Nótese que, cuando un lote termina, cada trabajo que aún no ha terminado incrementa la misma cantidad para su tiempo de finalización. Digamos que el primer lote de algún sufijo empieza en el trabajo $i$ y termina en el trabajo $k-1$. El tiempo invertido en procesar este lote sería $S + (P_{k-1} - P_{i-1}),$ donde $P$ es la suma de prefijos de los tiempos de procesamiento.

Todo trabajo a partir de $i$ debe esperar a que este lote termine, así que esta cantidad contribuye al costo de todos los trabajos restantes. Entonces, si $C_i$ denota la suma de sufijos de los factores de costo, elegir este lote sumará $\bigl(S+P_{k-1}-P_{i-1}\bigr)C_i$ a la respuesta. Así, podemos construir la transición de DP como

Como queremos minimizar el costo, tomando la mejor elección de $k$,

Sin embargo, si implementáramos la DP de forma directa, sería $O(N^2)$, lo cual es demasiado lento para las restricciones dadas.

Para optimizar la DP, podemos expandir la expresión.

Nótese que el segundo término no depende de $k$. Así, solo hay que minimizar $\texttt{dp}[k]+P_{k-1}C_i.$

Ahora esto parece una transición de CHT: cada estado $k$ es una recta $y = mx+b$ con $m = P_{k-1}$ y $b = \texttt{dp}[k].$ Para el estado actual $i$, podemos consultar la envolvente en $x=C_i.$ Entonces $mx+b = P_{k-1}C_i+\texttt{dp}[k],$ que es exactamente el valor que queremos.

Como las pendientes son sumas de prefijos, se insertan en orden monótono, y obtenemos una envolvente monótona. Como el valor de consulta es $C_i$, procesar los estados de $N$ hacia $1$ también da consultas monótonas. Cada $C_i$ es una suma de sufijos, así que crece a medida que nos movemos a la izquierda.

Esto significa que la mejor recta solo avanza en una dirección a través de la envolvente. Una vez que una recta es peor que la siguiente para la consulta actual, nunca volverá a ser óptima, así que podemos quitarla del deque. Así, un deque de envolvente convexa basta para resolver el problema en tiempo lineal.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <deque>
#include <iostream>
#include <vector>
 
int main() {
	int n, s;
	std::cin >> n >> s;
	std::vector<int> t(n + 1), f(n + 1);
	for (int i = 1; i <= n; i++) std::cin >> t[i] >> f[i];
 
	// calculate prefix sum of times
	std::vector<int> prefTime(n + 2);
	for (int i = 1; i <= n; i++) { prefTime[i] = prefTime[i - 1] + t[i]; }
 
	// calculate suffix sum of cost factors
	std::vector<int> sufCost(n + 2);
	for (int i = n; i >= 1; i--) { sufCost[i] = sufCost[i + 1] + f[i]; }
 
	// dp[i] = min cost for jobs i to n
	std::vector<int> dp(n + 2);
 
	std::deque<int> q;   // convex hull
	q.push_back(n + 1);  // no jobs left
 
	for (int i = n; i >= 1; i--) {
		// find the best transition point for current i
		while (q.size() > 1) {
			int first = q.back(), second = q[q.size() - 2];
 
			// check if newer line is better earlier
			if (sufCost[i] * (prefTime[first - 1] - prefTime[second - 1]) >=
			    dp[second] - dp[first]) {
				q.pop_back();
			} else {
				break;
			}
		}
 
		// k is the best transition point, as found using CHT
		int k = q.back();
		dp[i] = dp[k] + (s + prefTime[k - 1] - prefTime[i - 1]) * sufCost[i];
 
		// maintain convex hull
		while (q.size() > 1) {
			int first = q.front(), second = q[1];
 
			// pop middle line if never optimal
			if ((dp[i] - dp[first]) * (prefTime[second - 1] - prefTime[first - 1]) <=
			    (dp[first] - dp[second]) * (prefTime[first - 1] - prefTime[i - 1])) {
				q.pop_front();
			} else {
				break;
			}
		}
 
		q.push_front(i);  // add the current line
	}
 
	std::cout << dp[1] << '\n';
}