Convex hull trick

L'ottimizazione si può usare per transizioni del tipo:
${\text{dp}}_i=\underset{j<i}{min}({\text{dp}}_j+q_j+m_j{x}_i)$
Transizioni di questo tipo si possono interpretare come trovare il minimo in un punto per un insieme di rette.
Funziona solo se gli $x_i$ sono crescenti/decrescenti. Per casi più complicati è necessario il Li chao tree.

Risorse

• Blog cf

Problemi

• The fair nut and the rectangles implementazione della tecnica
• Usaco.guide
• Frog 3 implementazione
• Circular barn meno ovvio