|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.12.2013, 20:13 | #1 |
Новичок
Джуниор
Регистрация: 05.12.2013
Сообщений: 1
|
Задача про парники
Здравствуйте. Помогите, пожалуйста, с алгоритмом решения
Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов. Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами, параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной(С) и величины, пропорциональной площади парника(Стоимость клетки, S). Парник может накрывать только целое количество ячеек. Выяснить какие варианты строительства парников наименее затратны при условии, что закрытыми от не погоды оказываются все ячейки с огурцами. Для начала я делил C на S без остатка. Получается число(K), которое соответствует максимальному количеству пустых ячеек в парнике. Соответственно, необходимо разбить все поле на наименьшее количество парников, в которых будет <=K пустых клеток. Но каким образом это сделать? Был вариант сначала разбить на вертикальные и горизонтальные теплицы с шириной в 1 клетку(т.к. в любом случае придется закрывать все огурцы), а потом объединять, но я так и не смог это реализовать до конца. |
05.12.2013, 20:19 | #2 |
Форумчанин
Регистрация: 22.04.2013
Сообщений: 588
|
Я видно не понял. Просто строим парник на все поле сразу, в этом случае известной постоянной(С) будет только один раз, и парник выйдет дешевле. В чем еще прикол?
|
05.12.2013, 20:20 | #3 |
Форумчанин
Регистрация: 22.04.2013
Сообщений: 588
|
А, мы должны программно имитировать поле. Да.....
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
задача про трапеции | Lady_Makbet | Помощь студентам | 0 | 10.07.2012 12:43 |
Задача про хорды | Assasin92 | Помощь студентам | 11 | 03.04.2012 21:58 |
Задача про гиперкуб | Артём С. | Общие вопросы C/C++ | 0 | 01.04.2012 14:37 |
Задача про мандарины | Thunder Dragon | Паскаль, Turbo Pascal, PascalABC.NET | 6 | 26.03.2012 21:48 |
Задача про кирпич на С++ | Lana44 | Общие вопросы C/C++ | 1 | 04.02.2012 20:41 |