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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Mamai
Сообщений: n/a
#1

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

04.12.2013, 23:27. Просмотров 287. Ответов 0
Метки нет (Все метки)

Здравствуйте.
Задача по программированию, но, как мне кажется, у нее есть некий математический алгоритм решения.

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

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

Построить парники, закрывающие огурцы - C++
Нужно помочь с задачей. Задачу сдавать на зачёт, я не знаю как её сделать; она мне кажется очень сложной. Пишу на С++ Задача о огурцах....

Задача про биты - C++
Написать функцию, которая возвращает число, полученное из числа X,в котором все розряды, расположенные правее центральной позиции, заменены...

Задача про банку - C++
Вася живет в стране Осьляндии, где, как всем известно, люди хранят деньги в банках. На совершеннолетие родители подарили Васе новую чистую...

Задача про Лестницу - C++
Условия формулируются так: Есть лестница высотой в n ступенек (плюс «нулевая» - площадка, где мы стоим вначале). На каждой ступеньке...

Задача про числа - C++
Думаю, думаю, но всё равно не могу понять как решить. Задача: Дан массив из положительных чисел и два числа a и b. Мы можем отнять...

Задача про календарь - C++
Имеется задача: Два одноклассника Петя и Вася родились не ранее 1993 и не позднее 1994 года, причем, Петя старше Васи. Напишите...

задача про массивы - C++
упорядочить по убыванию положительные эл-ты массмва, сохраняя остальные эл-ты на прежних местах

Задача про метеостанции - C++
На южном полюсе расположены N пронумерованных метеорологических станций. Каждая станция соединена с другими станциями линиями связи. В...

Задача про год - C++
Есть такая задача. Дано число k (от 1 до 365). присвоить значение n (от 0 до 6) в зависимости от того, на какой день недели приходиться...

Задача про кузнечиков - C++
Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k столбиков. Найти количество вариантов,...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru