Optimisation de la puissance de combat dans un arbre de relations maître-disciple
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 ...
Publié le 13 août à 06h44
Techniques Avancées de Programmation Dynamique pour l'Algorithmique de Compétition
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 ...
Publié le 2 juin à 01h40