L'Atelier Monstre

Calcul de sous-tableaux à somme fixe Pour identifier rapidement les sous-sequences contiguës dont la somme équivaut à une valeur cible, la technique des sommes préfixées couplée à une table de dispersion s'avère optimale. En définissant P[j] comme la somme des éléments jusqu'à l'indice j, la somme d'un sous-tableau allant de i à j-1 s'exprime p ...

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 ...

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)$ comm ...