Башня ящиков (укладка кубов)

Question

Я получил эту задачу на прошлой неделе, но не могу найти хороший алгоритм для решения проблемы. Итак, вот описание:

Вы можете построить стабильную башню со строительными кубами, не кладя большие кубы в меньшие, а если не ставить более тяжелые кубики в более легкие. Создайте программу, которая даст вам максимально возможную башню с n количеством кубов.
Входные данные:
В первой строке in.txt указано количество кубов n (1 =Выход:
Вы должны записать максимально возможное число m стабильной башни в out.txt. во втором ряду вы должны написать порядковый номер башни m снизу вверх. под высотой башни мы подразумеваем количество всех сторон кубов (не количество кубов). если есть более одного решения, вы можете дать все, что вы хотите
пример для ввода и вывода:
вход:
5
10 3
20 5
15 6
15 1
10 2
и вывод:
3
2 1 5
Вот ограничения по программе. Ограничение времени: 0,2 сек. Ограничение памяти: 16 Мб

Я надеюсь, что вы можете помочь мне решить это. спасибо за помощь

Answer 1

Соотношение "блок A может быть помещено поверх блока B" определяет частичный порядок блоков. Вы можете использовать алгоритм Кана (он же "топологическая сортировка"), чтобы превратить его в общий порядок, который затем можно пройти в глубину, чтобы найти самый длинный путь.