Форум программистов, компьютерный форум CyberForum.ru

Задача про парники - C++

Восстановить пароль Регистрация
 
Mamai
Сообщений: n/a
04.12.2013, 23:27     Задача про парники #1
Здравствуйте.
Задача по программированию, но, как мне кажется, у нее есть некий математический алгоритм решения.

Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.
Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами,
параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной(С)
и величины, пропорциональной площади парника(Стоимость клетки, S). Парник может накрывать только целое количество ячеек. Выяснить какие варианты
строительства парников наименее затратны при условии, что закрытыми от не погоды оказываются все ячейки с огурцами.

Для начала я делил C на S без остатка. Получается число(K), которое соответствует максимальному количеству пустых ячеек в парнике. Соответственно, необходимо разбить все поле на наименьшее количество парников, в которых будет <=K пустых клеток.
Но каким образом это сделать?
Был вариант сначала разбить на вертикальные и горизонтальные теплицы с шириной в 1 клетку(т.к. в любом случае придется закрывать все огурцы), а потом объединять, но я так и не смог это реализовать до конца.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.12.2013, 23:27     Задача про парники
Посмотрите здесь:

C++ Задача про слона 0о
задача про массивы C++
C++ [C++] задача про вектор
Задача про монеты C++
C++ задача про N ферзей
Задача про календарь C++
C++ Задача про яйца
C++ Задача про небоскребы

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 13:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru