МЦНМО 3184

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Ссылка на задачу

Похожие задачи

Комментарии

Пусть в строке y самый левый объект имеет координату xl, а самый правый — координату xr. Утверждается, что из-за того, что перемещения по вертикали возможны только в одном направлении, нам потребуется покрыть весь отрезок [xl; xr].

Состояние динамики будет включать координаты текущей клетки, а также маску из 2k бит, кодирующую покрытие k последних горизонталей: биты 2i и 2i + 1 отвечают за покрытие начала и конца i-го ряда.