Клад Опции

[DarkWishmaster]

Привет. Вот задача с олимпиады.
Кладоискатели нашли в одном из замкнутых помещений средневекого замка N золотых слитков различных размеров. Каждый слиток представляем прямоугольный паралелипипед с рамзерами X*Y*Z. Для того чтобы извлечь слитки из замка, кладоискатели должны пробить в каменой стене одно или больше прямоугольных отверстий, которые не должны иметь точек соприкосновения. Слиток можно извлечь через отверстие только в том случае если , если ширина и высота отверстия равны или больше чем ширина и высота одной из прямоугольных граней паралелипипеда. Очевидно, слитки можно переворачивать произвольным образом.
Для того что-бы облегчить себе работу, кладоискатели желают что-бы площадь пробиваемых отверстий была наименьшей.
Пример:
n=3
1 4 4
5 3 2
1 2 2
Минимальная площадь: S=8
Вообще нету никаких идей на счет этой задачи. Может у вас есть? Только не надо сразу код, можно просто алгоритм.
1<=n<=5000;
1<=x,y,z<=10000;
время выполнения не должно превышать 3 сек.
обьем оперативной памяти не должен превышать 32 мегабайт.

Сообщение отредактировано: DarkWishmaster - 23.05.2011 4:01

[Lapp]

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

[DarkWishmaster]

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

Сортируем, потом по каким критериям брать слитки?
Можно взять слиток с наибольшей площадью, а на нем ставить все остальные менее большие слитки так что-бы всё совпало, потом из чего осталось опять выбираем самый большой слиток и.т

[Lapp]

Сортируем, потом по каким критериям брать слитки?
Можно взять слиток с наибольшей площадью, а на нем ставить все остальные менее большие слитки так что-бы всё совпало, потом из чего осталось опять выбираем самый большой слиток и.т

Это немного лучше, но все равно ты еще не навел порядок в мыслях.

Говори точнее. Что и по чему сортируем, что значит авыражение "на нем ставить"? Перед написанием кода весьма желательно достичь полной ясности в алгоритме. И уж конечно, в терминах. Даже если алгоритм не вполне определен, оперировать нужно строгими понятиями.

Жду четкого описания. Из того, что ты сказал в предыдущем посте, я мало, что понял. А строить догадки - извини, не тот случай.