L'Atelier Monstre

Modèle Mathématique et Interprétation Géométrique La technique de l'enveloppe convexe (Convex Hull Trick) est une méthode d'optimisation puissante utilisée pour accélérer certaines récurrences de programmation dynamique. Elle s'applique typiquement aux équations de transition de la forme suivante : \[ dp[i] = \min_{j < i} \{ dp[j] + A[i] + B ...

A. L'importance d'une lecture attentive des énoncés Cette quesiton implémentait une optimisation de la programmation dynamique à l'aide d'une file monotone, un schéma récurrent similaire à celui de la question C de la veille. B. Obtenir des points même avec une solution brute-force Le problème est basé sur P1758 [NOI2009] de Luogu. Il s'agit d' ...