Two Sawmills

Explicación

Definamos una función $f(a,b)$ que denota el costo cuando colocamos aserraderos en $a$ y $b$ , $a < b$ . Sea $T$ el costo de transportar todos los árboles a la base de la colina (es decir, el costo sin construir ningún aserradero). Denotemos dos arreglos $W$ y $D$ que representan la suma de prefijos del peso y de la distancia, respectivamente.

f(a, b) = T - W[a] \cdot (D[b] - D[a]) - W[b] \cdot (D[n + 1] - D[b])

Si mantenemos $b$ constante, podemos reordenar la ecuación en:

f(a, b) = T - W[a] \cdot D[b] + W[a] \cdot D[a] - W[b] \cdot D[n + 1] + W[b] \cdot D[b]

f(a, b) = \{(T + W[a] \cdot D[a]) - W[a] \cdot D[b]\} - W[b] \cdot D[n +1] + W[b] \cdot D[b]

Así, $f$ se puede descomponer en cuatro partes: $y_a = T + W[a] \cdot D[a]$ , $m_a = -W[a]$ , $x = D[b]$ , $c = -W[b] \cdot D[n + 1] + W[b] \cdot D[b]$ . Así,

f(a, b) = (y_a + m_ax) + c

Definamos otra función $g(b)$ que denota el costo mínimo si colocamos el segundo aserradero en $b$ . Esto se puede expresar simplemente en términos de $f(a,b)$ .

g(b) = \min_{1 \leq a < b} (y_a + m_a x) + c

Como $x$ y $c$ son funciones de $b$ , podemos mantenerlas constantes. Nótese que $y_a + m_a x$ forma una función lineal de $x$ . Podemos usar el truco de la envolvente convexa para consultar de forma eficiente el valor mínimo de un grupo de funciones lineales. La respuesta es simplemente $\max_{2 \leq b \leq N}g(b)$ .

Lo último que queda es calcular $T$ de forma eficiente.

T = w_1(d_1 + d_2 + \dots + d_n) + w_2(d_2 + d_3 + \dots + d_n) + \dots + w_n(d_n)

T = \sum_{1 \leq k \leq n} W[k] \cdot d_k

Complejidad temporal: $\mathcal{O}(n)$ o $\mathcal{O}(n \log n)$ según la implementación de CHT. Como la siguiente solución usa LineContainer, corre en $\mathcal{O}(n \log n)$ .

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Line Container}
/**
 * Source: /adv/line-container?lang=cpp
 */
bool _Line_Comp_State;
struct Line {
	// k is slope, m is intercept, p is intersection point
	mutable long long k, m, p;
	bool operator<(const Line &o) const { return _Line_Comp_State ? p < o.p : k < o.k; }
};
 
struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
 
	bool isect(iterator x, iterator y) {
		if (y == end()) {
			x->p = LLONG_MAX;
			return false;
		}
		if (x->k == y->k) {
			x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		} else {
			x->p = div(y->m - x->m, x->k - y->k);
		}
		return x->p >= y->p;
	}
	void add(long long k, long long m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) { z = erase(z); }
		if (x != begin() && isect(--x, y)) { isect(x, y = erase(y)); }
		while ((y = x) != begin() && (--x)->p >= y->p) { isect(x, erase(y)); }
	}
 
	long long query(long long x) {
		assert(!empty());
		_Line_Comp_State = 1;
		auto l = *lower_bound({0, 0, x});
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};
// EndCodeSnip
 
const int MAXN = 20000;
 
int N;
long long W[MAXN + 1], D[MAXN + 1], T;
 
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int w, d;
		cin >> w >> d;
		W[i] = W[i - 1] + w;
		D[i + 1] = D[i] + d;
		T += W[i] * d;
	}
 
	LineContainer lc;
	long long ans = LLONG_MAX;
	for (int i = 1; i <= N; i++) {
		if (i > 1) { ans = min(ans, -lc.query(D[i]) - W[i] * D[N + 1] + W[i] * D[i]); }
		// y intercept and slope are negative to query minimum instead of
		// maximum
		lc.add(W[i], -(T + W[i] * D[i]));
	}
 
	cout << ans << '\n';
}