Теоретический материал

Введение

К большинству олимпиадных задач ограничения (по времени, по памяти) жюри подбирает по принципу "как можно больше". То есть чтобы любые разумные реализации правильного решения проходили, а всё остальное -- нет.

Когда встречается задача с маленькими ограничениями (например, до 10), это означает, что либо автор намеренно сбивает Вас с правильного пути, либо действительно эта задача решается каким-то (оптимизированным) перебором.

Динамическое программирование по профилю -- одна из таких оптимизаций. Часто в таких задачах дело происходит на прямоугольной таблице, одна из размерностей которой достаточно мала (не более 10). Требуется проверить существование, посчитать количество способов, стоимость и т.д. (как в обычном динамическом программировании). Асимптотика алгоритма, основанного на этой идее, является экспоненциальной только по одной размерности, а по второй -- линейная или даже лучше.