Имеется некоторое число прямоугольников(спрайтов) c размерами Ni x Mi (Ni,Mi — целые числа). Каждый прямоугольник имеет различные размеры. Необходимо расположить их на произвольном(не обязательно минимальном) количестве квадратов(атласов) размером 2^Kx2^K (К — целое число ). Также необходимо минимизировать свободное пространство, образующееся при укладке. Спрайт нельзя крутить (это нужно для последующего извлечения спрайта из атласа). Ссылки на задачу нету — необходимо в промышленных целях =) Интересуют ваши идеи, мысли..
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 22:06:24 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Дейкстрой.дп по DAG(Direct Acyclic Graph)у нас есть n одинаковых прямоугольиков размера H на W. в один квадрат со стороной K мы их кладем один за другим слева направо сверху вниз. легко за O(1) сказать сколько прямоугольников влезет в квадрат с фиксированной стороной — (K div H) * (K div W). граф содержит вершины (n, k) — сколько у нас есть прямоугольников и текущий размер квадрата. переходы по графу это либо уменьшение размера квадрата и переход в вершину (n, k — 1) или запихивание максимального числа прямоугольников в квадрат данного размера и переход к (n — max_k, k) max_k — сколько влезло. стоимость второго перехода это размер свободного места, которое осталось в квадрате.
спасибо. очевидно что оптимально укладывать нужно таким способом, при условии что прямоугольники одинаковые. но по заданию есть прямоугольники различных размеров (этого не было перед тем как вы написали. уже исправил. понял что сам не точно описал задачу)
Это уже задача "раскройки", задача на оптимальное размещение. по моему её решают перебороподобными алгоритмами с отсечениями. В вашем случае наверное проще задействовать человека. Написать что-то вроде тетриса, где человек сможет мышкой таскать прямоугольники, и пусть пооптимизирует немного, убирая явные зазоры. не думаю что профит от офигенного размещения превосходит затраты на разработку офигенной программы, которая его достигает.