LineContainer

En lugar de enfocarnos en los pilares que deberían destruirse, enfoquémonos en los pilares que permanecen.

El costo total consiste en el costo por diferencias de altura más el costo de destruir los pilares no usados. Este último costo es igual al costo de destruir todos los pilares menos el costo de destruir los pilares restantes.

Como el costo de destruir todos los pilares es constante, podemos convertir el problema en uno de construir pilares en lugar de destruirlos.

Recursos
Fuente	Recurso	Notas
CF	Blogewoosh - Half-Plane Intersection w/ Ternary Search
Petr	Linear Half-Plane Intersection	¡Tiempo lineal esperado!

Fuente	Nombre	Dificultad	Tags	Solución
Kattis	Marshland Rescues	Normal		Solución
JOI	2017 - Dragon 2	Difícil		Solución
Balkan OI	2011 - 2circles	Muy difícil	Geometry, Binary Search	Solución

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Line Add Get Min	Normal		—

Recursos
Fuente	Recurso	Notas
KACTL	LineContainer	fuente del código que yo (Ben) uso
cp-algo	Li-Chao Tree	tema relacionado (pero no es lo mismo)

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CEOI	2017 - Building Bridges	Normal	DP, Convex	en el módulo

De esto obtenemos una recurrencia de DP básica. Sea

dp[i]

el costo mínimo para construir el puente de modo que el último pilar construido sea el pilar

i

describe de forma efectiva una función lineal

y = mx + c

, donde

m = -2h_j

x = h_i

c = dp[j] + h_j^2

Sin embargo, como

m

no es monótono, no podemos usar CHT lineal con un deque, así que debemos conformarnos con

\mathcal{O}(N \log N)

Aquí implementé CHT usando un std::set, pero otras implementaciones usando cosas como el Árbol de Li Chao deberían funcionar de forma similar.


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
struct Line {
	bool type;
	double x;
	ll m, c;
};
 
bool operator<(Line l1, Line l2) {
	if (l1.type || l2.type) return l1.x < l2.x;
	return l1.m > l2.m;
}
 
set<Line> cht;
ll h[100001], w[100001], tot = 0, dp[100001];
 
bool has_prev(set<Line>::iterator it) { return it != cht.begin(); }
bool has_next(set<Line>::iterator it) {
	return it != cht.end() && next(it) != cht.end();
}
 
double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
	return (double)(l1->c - l2->c) / (l2->m - l1->m);
}
 
void calc_x(set<Line>::iterator it) {
	if (has_prev(it)) {
		Line l = *it;
		l.x = intersect(prev(it), it);
		cht.insert(cht.erase(it), l);
	}
}
 
bool bad(set<Line>::iterator it) {
	if (has_next(it) && next(it)->c <= it->c) return true;
	return (has_prev(it) && has_next(it) &&
	        intersect(prev(it), next(it)) <= intersect(prev(it), it));
}
 
void add_line(ll m, ll c) {
	set<Line>::iterator it;
 
	it = cht.lower_bound({0, 0, m, c});
	if (it != cht.end() && it->m == m) {
		if (it->c <= c) return;
		cht.erase(it);
	}
 
	it = cht.insert({0, 0, m, c}).first;
	if (bad(it)) cht.erase(it);
	else {
		while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
		while (has_next(it) && bad(next(it))) cht.erase(next(it));
 
		if (has_next(it)) calc_x(next(it));
		calc_x(it);
	}
}
 
ll query(ll h) {
	Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
	return l.m * h + l.c;
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		tot += w[i];
	}
 
	dp[1] = -w[1];
	for (int i = 2; i <= n; i++) {
		add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
		dp[i] = query(h[i]) - w[i] + h[i] * h[i];
	}
 
	cout << tot + dp[n];
	return 0;
}

Intersección de semiplanos

LineContainer (también conocido como CHT $\mathcal{O}(N \log N)$ )

Problema de ejemplo

Análisis

Problemas