Решение: Коробки-матрёшки двух материалов
В магазине для упаковки подарков есть $N$ кубических коробок из материалов двух видов. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $D$ единиц меньше длины стороны другой коробки, при этом любые две соседние коробки сделаны из разных материалов. Известны длины сторон и материалы коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле сначала заданы $N$ и $D$, затем для каждой коробки указаны длина стороны и материал — $0$ или $1$. В ответ запишите два числа: сначала максимальное количество коробок, затем максимально возможную длину стороны самой маленькой коробки. Для решения необходимы данные из прилагаемого входного файла.
Решение по шагам
5 шаговЗапишем каждую коробку как пару: длина стороны и материал. Отсортируем коробки по длине стороны.
Для коробки длины $x$ и материала $c$ допустимым предшественником является коробка материала $1-c$ с длиной не более $x-D$.
Для каждой группы коробок, проходя массив слева направо, найдём лучшие значения для обоих материалов среди ранее обработанных коробок. Чтобы не использовать коробку раньше времени, сначала вычислим значения для текущей группы, а затем добавим её в структуру лучших результатов.
Длина цепочки для текущей коробки равна единице плюс лучшая длина цепочки для противоположного материала среди допустимых предшественников. Одновременно сохраняем длину самой маленькой коробки в цепочке.
В конце выбираем цепочку с наибольшим количеством коробок. Если таких цепочек несколько, выбираем ту, у которой длина самой маленькой коробки максимальна.
Точный ответ невозможно вычислить без содержимого прилагаемого входного файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывать обязательное чередование материалов.
Проверять разность длин как строго больше $D$, хотя требуется не менее $D$.
Разрешать использовать коробки с одинаковой длиной, если условие $D=0$ не выполнено.
Обновлять лучшие значения внутри одной группы до обработки всех коробок этой группы и тем самым использовать одну и ту же коробку повторно.