А вот и не динамика! SRM 453 Div 1 500.

Прикольную задачку решил на днях.
Спортивный турнир, играют N команд. За победу команда получает w очков, за ничью d. Дано, какая команда сколько набрала очков в конце турнира(Points[i]).
Требуется подсчитать минимальное суммарное количество игр, которое должны сыграть команды, чтобы получить такие очки, либо вывести, что такая комбинация очков не возможна.

Обозначим максимально число очков S(в условии задачи не превосходило 10000). Кстати, N по условию не превосходило 50.

Сразу в голову приходит динамика, но я не смог придумать лучше, чем O(N * S * S), что понятно не успевает.
Однако, есть довольно простое и интересное решение.
Наблюдения:
1. Нужно либо максимизировать, либо минимизировать суммарное число ничьих.
2. Пусть D[i] число ничьих, которые сыграла команда i. Тогда конфигурация D[1], ...D[N} ничьих описывает корректный турнир, тогда и только тогда, когда сумма всех элементов четна, и удвоенные максимальный элемент не должен превосходить сумму всех элементов.

Пусть gcd = GCD(d, w); -- GCD = наибольший общий делитель.

Таким образом нам достаточно на начальном шаге D[i] максимально возможным, так что существует число побед W[i] i-й команды, что D[i] * d + W[i] * w == Points[i];

А затем производить итерации, каждый раз делая, пока возможно:
1. Проверяем корректность текущей конфигурации пункты (1 и 2). Если корректна, то обновляем минимально число матчей.
2. Полагаем D[i] = D[i] - w / gcd;

Если каждый раз максимальный элемент выбирать за O(N), то сложность получается O(N * N * S). Что достаточно для решения задачи. Однако, можно поддерживать очередь с приоритетами, и сложность падает до O(N * Log(N) * S). А с помощью двух списков вообще можно сделать за O(N * S).