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[j] + X[i] \cdot Y[j] \} \]

Où \(A[i]\) et \(X[i]\) sont des termes dépendant uniquement de \(i\), tandis que \(B[j]\) et \(Y[j]\) dépendent uniquement de \(j\). Le même prnicipe s'applique si l'on cherche à maximiser (\(\max\)) au lieu de minimiser.

Pour transformer cette équation, nous pouvons la réorganiser pour isoler les termes liés à \(j\) :

\[ dp[i] = A[i] + \min_{j < i} \{ Y[j] \cdot X[i] + (dp[j] + B[j]) \} \]

Cette expression peut être interprétée géométriquement comme un ensemble de droites. Si nous définissons :

• La pente \(m_j = Y[j]\)
• L'ordonnée à l'origine \(c_j = dp[j] + B[j]\)
• La variable \(x_i = X[i]\)

L'équation devient alors \( dp[i] = A[i] + \min_{j < i} \{ m_j \cdot x_i + c_j \} \). Le problème se réduit donc à trouver, parmi un ensemble de droites \(y = m_j x + c_j\), celle qui donne la valeur minimale de \(y\) pour un \(x_i\) donné.

Géométriquement, pour un \(x\) fixé, la droite optimale sera toujours celle qui forme la frontière inférieure de l'ensemble des droites. Cette frontière est appelée enveloppe convexe inférieure. Les droites qui ne font pas partie de cette enveloppe sont inutiles et peuvent être éliminées, car elles ne seront jamais optimales pour aucune valeur de \(x\).

Choix de la Structure de Données selon la Monotonie

La complexité et la structure de données à utiliser dépendent des propriétés de monotonie de \(x_i\) et de \(m_j\) :

• \(x_i\) et \(m_j\) sont tous deux monotones : Une file monotone (deque) suffit pour maintenir l'enveloppe convexe en temps \(O(N)\).
• Seul \(x_i\) est monotone : L'enveloppe convexe peut être maintenue, mais la recherche de la droite optimale nécessite une recherche dichotomique, portant la complexité à \(O(N \log N)\).
• Aucun des deux n'est monotone : Il faut recourir à des structures plus complexes comme l'arbre de Li Chao (Li Chao Tree), un arbre équilibré (std::set), ou la méthode de diviser pour régner CDQ (CDQ Divide and Conquer).

Implémentation de Base avec File Monotone

Voici une implémentation optimisée pour le cas où \(x_i\) et \(m_j\) sont tous deux monotones. Contrairement aux approches naïves utilisant des nombres à virgule flottante pour calculer les pentes, cette version utilise la multiplication croisée avec des entiers 128 bits pour éviter toute erreur de précision.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 100005;
long long dp[MAX_N];
int q[MAX_N]; // File monotone stockant les indices
int q_head = 0, q_tail = 0;

// Fonctions pour extraire la pente et l'ordonnée à l'origine
long long get_m(int j) { return Y[j]; }
long long get_c(int j) { return dp[j] + B[j]; }
long long eval(int j, long long x) { return get_m(j) * x + get_c(j); }

// Vérifie si la droite 'v' est rendue redondante par 'u' et 'w'
// Utilise __int128 pour éviter les débordements lors de la multiplication croisée
bool is_redundant(int u, int v, int w) {
    return (__int128)(get_c(w) - get_c(u)) * (get_m(u) - get_m(v)) <= 
           (__int128)(get_c(v) - get_c(u)) * (get_m(u) - get_m(w));
}

void solve(int n) {
    q[q_tail++] = 0; // Initialisation avec le premier état
    
    for (int i = 1; i <= n; ++i) {
        // Éliminer les droites non optimales en tête de file
        while (q_tail - q_head >= 2 && eval(q[q_head], X[i]) >= eval(q[q_head + 1], X[i])) {
            q_head++;
        }
        
        // Transition DP
        int best_j = q[q_head];
        dp[i] = eval(best_j, X[i]) + A[i];
        
        // Maintenir l'enveloppe convexe inférieure en queue de file
        while (q_tail - q_head >= 2 && is_redundant(q[q_tail - 2], q[q_tail - 1], i)) {
            q_tail--;
        }
        q[q_tail++] = i;
    }
}

Étude de Cas : Construction d'Entrepôts (P2120)

Prenons un problème classique de construction d'entrepôts sur une ligne. L'équation de transition brute s'écrit :

\[ dp[i] = \min_{j < i} \left\{ dp[j] + C[i] + \sum_{k=j+1}^{i} P[k] \cdot (D[i] - D[k]) \right\} \]

Pour optimiser cette somme, nous introduisons deux tableaux de sommes préfixées :

• \(S_P[i] = \sum_{k=1}^i P[k]\)
• \(S_{PD}[i] = \sum_{k=1}^i (P[k] \cdot D[k])\)

En développant et en substituant les sommes préfixées, l'équation se simplifie ainsi :

\[ dp[i] = \min_{j < i} \left\{ dp[j] + C[i] + D[i] \cdot (S_P[i] - S_P[j]) - (S_{PD}[i] - S_{PD}[j]) \right\} \]

\[ dp[i] = C[i] + D[i] \cdot S_P[i] - S_{PD}[i] + \min_{j < i} \left\{ -S_P[j] \cdot D[i] + dp[j] + S_{PD}[j] \right\} \]

Nous pouvons maintenant mapper cette expressino à notre modèle standard \( \min \{ m_j \cdot x_i + c_j \} \) :

• \(x_i = D[i]\) (La coordonnée \(x\) est monotone croissante si les positions sont triées).
• \(m_j = -S_P[j]\) (La pente est monotone décroissante car \(P[k] \ge 0\)).
• \(c_j = dp[j] + S_{PD}[j]\).

Puisque nous cherchons un minimum avec une pente décroissante et un \(x\) croissant, nous maintenons une enveloppe convexe inférieure standard. Voici l'implémentation spécifique à ce problème :

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
const int MAX_N = 100005;
const ll INF = 1e18;

ll D[MAX_N], P[MAX_N], C[MAX_N];
ll sum_P[MAX_N], sum_PD[MAX_N];
ll dp[MAX_N];
int q[MAX_N];
int qh = 0, qt = 0;

ll get_m(int j) { return -sum_P[j]; }
ll get_c(int j) { return dp[j] + sum_PD[j]; }
ll eval(int j, ll x) { return get_m(j) * x + get_c(j); }

bool is_redundant(int u, int v, int w) {
    return (__int128)(get_c(w) - get_c(u)) * (get_m(u) - get_m(v)) <= 
           (__int128)(get_c(v) - get_c(u)) * (get_m(u) - get_m(w));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    if (!(cin >> n)) return 0;
    
    // Ajout d'une sentinelle pour sécuriser les accès hors limites si nécessaire
    D[n + 1] = 3e9; 
    
    for (int i = 1; i <= n; ++i) {
        cin >> D[i] >> P[i] >> C[i];
        sum_P[i] = sum_P[i - 1] + P[i];
        sum_PD[i] = sum_PD[i - 1] + P[i] * D[i];
    }
    
    q[qt++] = 0; // L'état initial 0 est toujours valide
    
    for (int i = 1; i <= n; ++i) {
        // Avancer la tête de la file tant que la droite suivante est meilleure
        while (qt - qh >= 2 && eval(q[qh], D[i]) >= eval(q[qh + 1], D[i])) {
            qh++;
        }
        
        int best_j = q[qh];
        dp[i] = eval(best_j, D[i]) + C[i] + D[i] * sum_P[i] - sum_PD[i];
        
        // Nettoyer la queue pour maintenir la convexité
        while (qt - qh >= 2 && is_redundant(q[qt - 2], q[qt - 1], i)) {
            qt--;
        }
        q[qt++] = i;
    }
    
    cout << dp[n] << "\n";
    return 0;
}