HDU - 3480 présente deux techniques d'optimisation de DP : l'optimisation par pente et l'inégalité quadrilatérale.

1. Optimiastion par pente

Le code suivant illustre une implémentation classique avec une file monotone :

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9 + 7;
const int MAXM = 1e5 + 10;
const int MAXN = 1e4 + 10;

int val[MAXN], dp[MAXN][MAXN];
int q[MAXN], head, tail;
int ans[100001];

int compute_numerator(int i, int k1, int k2) {
    return (dp[i-1][k1] + val[k1+1] * val[k1+1]) - (dp[i-1][k2] + val[k2+1] * val[k2+1]);
}

int compute_denominator(int k1, int k2) {
    return 2 * (val[k1+1] - val[k2+1]);
}

int calculate_dp(int i, int j, int k) {
    return dp[i-1][k] + (val[j] - val[k+1]) * (val[j] - val[k+1]);
}

int main() {
    int n, m, T;
    cin >> T;
    for (int kase = 1; kase <= T; ++kase) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            cin >> val[i];
        sort(val + 1, val + 1 + n);
        for (int i = 1; i <= n; ++i)
            dp[1][i] = (val[i] - val[1]) * (val[i] - val[1]);

        for (int i = 2; i <= m; ++i) {
            head = tail = 0;
            q[tail++] = i - 1;

            for (int j = i; j <= n; ++j) {
                while (head + 1 < tail && compute_numerator(i, q[head+1], q[head]) < compute_denominator(q[head+1], q[head]) * val[j])
                    ++head;
                dp[i][j] = calculate_dp(i, j, q[head]);

                while (head + 1 < tail && 
                       compute_numerator(i, j, q[tail-1]) * compute_denominator(q[tail-1], q[tail-2]) <=
                       compute_numerator(i, q[tail-1], q[tail-2]) * compute_denominator(j, q[tail-1]))
                    --tail;
                q[tail++] = j;
            }
        }
        ans[kase] = dp[m][n];
    }

    for (int i = 1; i <= T; ++i)
        cout << "Case " << i << ": " << ans[i] << endl;

    return 0;
}

Bien que l’optimisation en mémoire avec un tableau circulaire soit possible, elle a été omise ici par choix — la complexité de refactorisation étant jugée inutile.

Caractéristiques clés de l’optimisation par pente :

• Généralement appliquée à des problèmes unidimensionnels.
• Utilise une file monotone (simulable via un tableau).
• Les transitions contiennent des termes quadratiques ou produits croisés.
• La dérivation repose souvent sur l’identité remarquable : $(a - b)^2 = a^2 - 2ab + b^2$.

Forme générale typique : $$ dp[i] = \min(dp[i], A \cdot dp[j] + i \cdot j + C) $$ où $ i \cdot j $ est une expression produit entre les indices.

La clé réside dans la manipulation algébrique pour isoler une pente, permettant d’éliminer les décisions dominées.

Considérons un exemple concret issu d’un problème similaire à HDU :

$$ dp[i] = \min\left( dp[i],\ dp[j] + m + (sum[i] - sum[j])^2 \right) $$

Soient deux candidats $ j $ et $ k $, avec $ k < j $. Si $ j $ est meilleur :

$$ dp[j] + (sum[i] - sum[j])^2 \leq dp[k] + (sum[i] - sum[k])^2 $$

Après développement et simplification :

$$ dp[j] + sum[j]^2 - (dp[k] + sum[k]^2) \leq 2 \cdot sum[i] \cdot (sum[j] - sum[k]) $$

Cela permet de définir une condition de comparaison basée sur une pente.

2. Optimisation par inégalité quadrilatérale

Code optimisé :

#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
int t;
int n, m;
int dp[5001][10001];
int opt[5001][10001]; // position optimale
int a[10001];

void solve() {
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; ++i)
        opt[0][i] = 1;

    dp[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
        dp[i][i] = 0;
        opt[i][i] = i;
        opt[i][n+1] = n;

        for (int j = n; j > i; --j) {
            for (int k = opt[i-1][j]; k <= opt[i][j+1]; ++k) {
                int cost = dp[i-1][k-1] + (a[j] - a[k]) * (a[j] - a[k]);
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    opt[i][j] = k;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    for (int case_id = 1; case_id <= t; ++case_id) {
        cin >> n >> m;
        memset(dp, 0x3f, sizeof(dp));
        solve();
        cout << "Case " << case_id << ": " << dp[m][n] << '\n';
    }

    return 0;
}

Ce code est plus concis mais moins intuitif à justifier. Il repose sur la propriété de monotonie de la position optimale : Si $ opt[i][j] $ est la meilleure décision pour passer de $ i $ à $ j $, alors cette valeur est croissante avec $ j $.

Cette structure est valide lorsque la fonction de coût satisfait l’inégalité quadrilatérale : $$ dp[i][j] + dp[i+1][j+1] \leq dp[i][j+1] + dp[i+1][j] $$

Cela garantit que les positions optimales sont monotonnes, permettant une recherche bornée.

Exemple de tableau montrant la structure :

Les valeurs montrent une progression croissante dans chaque ligne, ce qui rend l’optimisation applicable.

En fin de compte, les deux méthodes visent à éliminer prématurément les décisions non optimales, en exploitant des propriétés structurelles du problème.