Coloriage de Parenthèses (DP par intervalles)

Ce problème classique de programmation dynamique par intervalles nécessite d'abord d'identifier les paires de parenthèses correspondantes à l'aide d'une pile. Pour un intervalle $[l, r]$, le coloriage n'a de sens que si les parenthèses sont appariées. Nous définissons l'état $f(l, r, c_1, c_2)$ comme le nombre de façons de colorer l'intervalle $[l, r]$ avec la couleur $c_1$ à l'extrémité gauche et $c_2$ à l'extrémité droite.

Les règles de transition dépendent de la structure de l'intervalle :

• Si $(l, r)$ est une paire directe : les combinaisons valides sont (0,1), (1,0), (0,2), (2,0) avec une valeur de 1.
• Si $l$ et $r$ sont appariés mais contiennent un sous-bloc : on calcule récursivement l'intérieur $[l+1, r-1]$ et on étend les couleurs en respectant les contraintes d'adjacence.
• Si $l$ n'est pas apparié à $r$ : on divise l'interavlle au point de correspondance de $l$, soit $match[l]$, et on applique le principe multiplicatif entre $[l, match[l]]$ et $[match[l]+1, r]$.

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
ll memo[705][705][3][3];
int partenaire[705];

void calculer_dp(int g, int d) {
    if (g + 1 == d) {
        memo[g][d][0][1] = memo[g][d][1][0] = memo[g][d][0][2] = memo[g][d][2][0] = 1;
        return;
    }
    if (partenaire[g] == d) {
        calculer_dp(g + 1, d - 1);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (i != 1) memo[g][d][1][0] = (memo[g][d][1][0] + memo[g + 1][d - 1][i][j]) % MOD;
                if (i != 2) memo[g][d][2][0] = (memo[g][d][2][0] + memo[g + 1][d - 1][i][j]) % MOD;
                if (j != 1) memo[g][d][0][1] = (memo[g][d][0][1] + memo[g + 1][d - 1][i][j]) % MOD;
                if (j != 2) memo[g][d][0][2] = (memo[g][d][0][2] + memo[g + 1][d - 1][i][j]) % MOD;
            }
        }
    } else {
        int miroir = partenaire[g];
        calculer_dp(g, miroir);
        calculer_dp(miroir + 1, d);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 3; ++k) {
                    for (int l = 0; l < 3; ++l) {
                        if (!(j == 1 && k == 1) && !(j == 2 && k == 2)) {
                            memo[g][d][i][l] = (memo[g][d][i][l] + memo[g][miroir][i][j] * memo[miroir + 1][d][k][l]) % MOD;
                        }
                    }
                }
            }
        }
    }
}

Organisation de Chansons (Bitmask DP)

Pour maximiser le nombre de chansons pouvant être jouées à la suite, nous utilisons la compression d'état (bitmask). Étant donné le faible nombre de chansons, nous définissons dp[mask][last] comme un booléen indiquant s'il est possible d'avoir l'ensemble de chansons représenté par mask se terminant par la chanson last.

Deux chansons sont compatibles si elles partagent le même auteur ou le même genre. Le résultat final est calculé en soustrayant le nombre maximum de bits activés dans un état valide au nombre total de chansons.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Chanson { string titre, auteur; };

void resoudre() {
    int n; cin >> n;
    vector<Chanson> v(n);
    for(int i=0; i<n; ++i) cin >> v[i].titre >> v[i].auteur;

    vector<vector<bool>> compatible(n, vector<bool>(n, false));
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            if(v[i].titre == v[j].titre || v[i].auteur == v[j].auteur)
                compatible[i][j] = true;

    vector<vector<bool>> dp(1 << n, vector<bool>(n, false));
    for(int i=0; i<n; ++i) dp[1 << i][i] = true;

    int max_selection = 0;
    for(int m=0; m < (1 << n); ++m) {
        for(int i=0; i<n; ++i) {
            if(dp[m][i]) {
                max_selection = max(max_selection, (int)__builtin_popcount(m));
                for(int j=0; j<n; ++j) {
                    if(!(m & (1 << j)) && compatible[i][j])
                        dp[m | (1 << j)][j] = true;
                }
            }
        }
    }
    cout << n - max_selection << endl;
}

Rudolf et les k Ponts (Optimisation par File Monotone)

Ce problème demande de trouver le coût minimal pour construire des ponts sur des rivières. Pour chaque rivière, le coût de construction d'un pilier à la position $j$ dépend de la valeur minimale des piliers précédents dans un rayon de distance $d$. L'utilisation d'une file monotone (deque) permet d'optimiser la transition DP de $O(M^2)$ à $O(M)$.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

void traiter_cas() {
    long long n, m, k, d;
    cin >> n >> m >> k >> d;
    vector<long long> couts_rivieres(n);
    for(int i=0; i<n; ++i) {
        vector<long long> a(m), dp(m);
        for(int j=0; j<m; ++j) cin >> a[j];
        
        deque<int> dq;
        dp[0] = 1;
        dq.push_back(0);
        for(int j=1; j<m; ++j) {
            while(!dq.empty() && dq.front() < j - d - 1) dq.pop_front();
            dp[j] = dp[dq.front()] + a[j] + 1;
            while(!dq.empty() && dp[dq.back()] >= dp[j]) dq.pop_back();
            dq.push_back(j);
        }
        couts_rivieres[i] = dp[m-1];
    }
    
    long long somme_actuelle = 0, min_total = 1e18;
    for(int i=0; i<n; ++i) {
        somme_actuelle += couts_rivieres[i];
        if(i >= k) somme_actuelle -= couts_rivieres[i-k];
        if(i >= k - 1) min_total = min(min_total, somme_actuelle);
    }
    cout << min_total << endl;
}

Tondre la Pelouse (Optimisation Monotone)

L'objectif est de maximiser la somme des éléments sélectionnés sans jamais en prendre plus de $K$ consécutifs. Soit $S[i]$ la somme préfixe. L'équation de transition est $dp[i] = \max(dp[j-1] + S[i] - S[j])$ pour $i-K \leq j \leq i$. En isolant les termes dépendant de $j$, on cherche à maximiser $dp[j-1] - S[j]$, ce qui se résout efficacement avec une file monotone.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> val(n + 1), pref(n + 1, 0);
    for(int i=1; i<=n; ++i) {
        cin >> val[i];
        pref[i] = pref[i-1] + val[i];
    }
    
    vector<long long> dp(n + 1, 0);
    auto calc = [&](int j) { return dp[j-1] - pref[j]; };
    deque<int> dq;
    dq.push_back(0);
    
    for(int i=1; i<=n; ++i) {
        while(!dq.empty() && dq.front() < i - k) dq.pop_front();
        // Cas i-k == 0 géré par l'initialisation
        if (i <= k) dp[i] = pref[i];
        
        // On compare avec la meilleure option de repos
        dp[i] = pref[i] + calc(dq.front());
        
        // Mise à jour de la file avec le nouveau dp[i-1]-pref[i]
        // Note: i+1 sera le prochain j potentiel
        while(!dq.empty() && calc(dq.back()) <= calc(i)) dq.pop_back();
        dq.push_back(i);
    }
    cout << dp[n] << endl;
    return 0;
}

Reconstruction de Routes (DP sur Arbre)

Ce problème demande de trouver le nombre minimal d'arêtes à supprimer pour isoler un sous-arbre de taille exactement $P$. Il s'agit d'une variante du problème du sac à dos appliqué sur une structure arborescente. L'état $dp[u][i]$ représente le coût minimal pour obtenir une composante de taille $i$ enracinée en $u$.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e8;
vector<int> adj[305];
int f[305][305];
int taille[305], degre_out[305];
int N, P;

void dfs(int u) {
    taille[u] = 1;
    f[u][1] = degre_out[u];
    for(int v : adj[u]) {
        dfs(v);
        taille[u] += taille[v];
        for(int i = min(P, taille[u]); i >= 1; --i) {
            for(int j = 1; j < i; ++j) {
                f[u][i] = min(f[u][i], f[u][i-j] + f[v][j] - 1);
            }
        }
    }
}

int main() {
    cin >> N >> P;
    for(int i=0; i<N-1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        degre_out[u]++;
    }
    for(int i=1; i<=N; ++i)
        for(int j=1; j<=P; ++j) f[i][j] = INF;
        
    dfs(1);
    int ans = f[1][P];
    for(int i=2; i<=N; ++i) ans = min(ans, f[i][P] + 1);
    cout << ans << endl;
    return 0;
}

Cows in a Skyscraper (Bin Packing avec Bitmask)

Pour répartir des objets dans un minimum de conteneurs de capacité $W$, nous utilisons deux tableaux : dp[mask] pour le nombre minimal de conteneurs et libre[mask] pour l'espace restant dans le dernier conteneur. Pour chaque état, on tente d'ajouter un nouvel objet en optimisant d'abord le nombre de conteneurs, puis l'espace libre.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    long long w;
    cin >> n >> w;
    vector<long long> poids(n);
    for(int i=0; i<n; ++i) cin >> poids[i];

    vector<int> nb_bacs(1 << n, n + 1);
    vector<long long> reste(1 << n, 0);

    nb_bacs[0] = 1;
    reste[0] = w;

    for(int s=0; s < (1 << n); ++s) {
        for(int i=0; i<n; ++i) {
            if(!(s & (1 << i))) {
                int nouvel_etat = s | (1 << i);
                int bacs = nb_bacs[s];
                long long r = reste[s];

                if(r >= poids[i]) {
                    r -= poids[i];
                } else {
                    bacs++;
                    r = w - poids[i];
                }

                if(bacs < nb_bacs[nouvel_etat]) {
                    nb_bacs[nouvel_etat] = bacs;
                    reste[nouvel_etat] = r;
                } else if(bacs == nb_bacs[nouvel_etat]) {
                    reste[nouvel_etat] = max(reste[nouvel_etat], r);
                }
            }
        }
    }
    cout << nb_bacs[(1 << n) - 1] << endl;
    return 0;
}