L'Atelier Monstre

La programmation dynamique (DP) repose sur la décomposition d'un problème complexe en sous-problèmes plus simples, en stockant les résultats pour éviter des calculs redondants. Avant d'aborder le problème du sac à dos, il est essentiel de maîtriser les fondements suivants : Cheminement dans une grille : Définir dp[i][j] comme le nombre de chem ...

Jeux de pierres premières Le théorème de Zermelo établit que chaque position est soit gagnante soit perdante avec une stratégie optimale. On définit 0 comme position perdante. Une position est gagnante si elle permet de laisser une position perdante à l'adversaire. Une position est perdante si toutes les actions conduisent à une position gagnan ...

Sous-matrice de somme maximale Énoncé. On représente la « taille » d’une matrice par la somme de tous ses éléments. Étant donné une matrice carrée N × N, trouver la plus grande sous-matrice non vide (au moins 1 × 1) au sens de cette somme. Par exemple, dans la matrice 4 × 4 suivante : 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 La sous-mat ...

On a un groupe de combattants organisés en un arbre, où chaque combattant a un maître (sauf le chef). Chaque combattant a une certaine puissance de combat. Le but est d'inviter certains combattants pour maximiser la somme de leur puissance, tout en respectant la contrainte que si un maître est invité, aucun de ses disciples ne peut l'être. Form ...

Codage de Huffman et Optimisation Greedy Pour minimiser le coût total d'un arbre de codage, l'approche gloutonne de Huffman est optimale. En utilisant une file de priorité (tas binaire), nous extrayons répétitivement les deux poids les plus faibles pour construire l'arbre de bas en haut. import heapq def calculer_cout_huffman(): n = int(in ...

Analyse du Problème de Parenthèses Valides Ce défi algorithmique consiste à analyser une chaîne de caractères composée exclusivement de parenthèses ouvrantes ( et fermantes ). L'objectif est d'identifier la longueur maximale d'une sous-chaîne continue qui respecte la syntaxe correcte des parenthèses. Visualisation de la Logique Pour comprendre ...

L'analyse d'un problème de type réseau de flux met en évidence une réduction à un problème d'optimisation. La solution consiste à construire un graphe auxiliaire avec une source et un puits fictifs pour gérer les déséquilibres de flux. Chaque arc original est modélisé par plusieurs arêtes possibles pour permettre la correction du flux et de la ...

Problème A : Somme de Produits Triangulaires Description : Étant donné trois entiers positifs \(A\), \(B\) et \(C\), calculer la valeur modulo \(998244353\) de la somme triple \(\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} a \times b \times c\). Solution : La somme se factorise en \(\left( \sum_{a=1}^{A} a \right) \times \left( \sum_{b=1}^{B} b ...

Problème G: Théorie des jeux avec Rikka Énoncé du problème: Étant donné un graphe non oreinté à n sommets (n ≤ 17), attribuer une valeur à chaque sommet telle que la valeur de chaque sommet soit le mex des valeurs des sommets adjacents. Calculer le nombre total d'attribution valide. Solution: La contrainte sur n suggère une approche par program ...

Maison Voleur Ce problème est analogue à une version non continue de la somme maximale d'une sous-séquence. En séparant le dernier élément, les parties précédentes forment un sous-problème. La solution utilise la programmation dynamique pour calculer le maximum sans voler deux maisons adjacentes. class Solution { public: int rob(vector&l ...