Algorithmes avancés pour problèmes de programmation compétitive
A. Sous-tableau maximum à deux segments
Algorithme standard du sous-tableau maximum :
for (int idx = 1; idx <= n; idx++)
cumul[idx] = max(cumul[idx - 1] + valeurs[idx], valeurs[idx]);
cumul[i] représente la somme maximale se terminant à la position i, calculée à partir de la valeur précédente ou en recommençant une nouvelle séquence.
S ...
Publié le 8 juillet à 20h47
Solutions Combinatoires pour des Problèmes de Compétition en Programmation
A. Génération de Chaînes Binaires (P6191)
On commence par compter les solutions avec 0 ou 1 seul '1'. Ensuite, on modélise la séquence comme une succession de blocs "1 suivi de k zéros", terminée par un '1'. Pour i occurrences de '1', la longueur minimale est j = (k + 1)(i - 1) + 1. Si j dépasse n, on arrête. Sinon, on calcule le nomb ...
Publié le 7 juin à 03h14