С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
1

Двумерное ДП

05.01.2014, 19:27. Просмотров 882. Ответов 3
Метки нет (Все метки)

Здравствуйте! Сейчас я изучаю такой интереснейший раздел, как ДП.Но вот с ним возникают серьезные проблемы. И вот проблема с задачей на двумерное ДП. Условие задачи:

После решения задачи с пашней земли, фермер хочет построить на этой земле как можно больший по площади сарай прямоугольной формы. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Для простоты представим ферму прямоугольной сеткой размера MxN. Каждое из деревьев и построек размещается в одном или нескольких узлах сетки. Сарай должен быть построен на свободных узлах сетки.

Помогите фермеру определить максимально возможную площадь сарая.

Входные данные

В первой строке входного файла INPUT.TXT записаны два натуральных числа N и M (1 ≤ N,M ≤ 1000) – размеры фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) из M нулей и единиц, описывающих ферму. Единицы соответствуют свободным для постройки участкам.

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь сарая, который может построить фермер на своем участке.



Как тут организовать динамику?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2014, 19:27
Ответы с готовыми решениями:

Двумерное БПФ
Рассмотрим сначала одномерный случай. Пусть x(t), y(t) две действительные...

Быстрое двумерное дискретное преобразование Фурье
быстрое двумерное дискретное преобразование Фурье 2D FFT как это сделать для...

Двумерное дерево отрезков или фенвика + сканирующая прямая
Интересно было бы порешать задачи на эту тему, киньте что-нибудь

Двумерное преобразование Фурье
!!!!!!!!!!!! ПОЖАЛУЙСТА ПОМОГИТЕ!!!!!! Нужно было отфильтровать изображение с...

Двумерное создание label ов
Добрый день всем. Ребята подскажите как при помощи двумерного массива создать...

3
programina
2053 / 608 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
05.01.2014, 19:51 2

Не по теме:

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Как тут организовать динамику?
Фермеру нужны инвестиции для стартапа.



По задаче: нужно найти интервалы по длине и ширине, произведение которых даст максимальную площадь.
1
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
05.01.2014, 20:07  [ТС] 3
programina, хм, это я понял.А КАК это сделать?
0
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
05.01.2014, 20:54 4
http://e-maxx.ru/algo/maximum_zero_submatrix
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2014, 20:54

Двумерное вейвлет-преобразование
Есть ли какой-нибудь стандартный двумерный алгоритм вейвлет-преобразования, где...

Двумерное преобразование фурье
Где б разжиться функцией двумерного преобразования фурье? Причем, желательно,...

Двумерное уравнение теплопроводности.
Решаю очень похожую задачу,разобралась с прогонкой. Там д.б. на каждом слое...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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