Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3740 |
3 | Radewoosh | 3652 |
4 | Benq | 3626 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3587 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3485 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 163 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | atcoder_official | 155 |
4 | nor | 155 |
6 | cry | 153 |
7 | -is-this-fft- | 152 |
8 | maroonrk | 151 |
9 | SecondThread | 148 |
10 | Petr | 146 |
Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
Название |
---|
быть может это поможет Вам: Your text to link here...
спасибо, после 40 минут просмотра и разбора я вроде бы понял эту статью. Но у меня созрел вопрос: чем отличается stack от vector-а? Вроде бы и там и там с одной стороны засовывают и с одной забирают.
Меня часто пытаются переубедить, но мне кажется, что std::stack побыстрее, чем std::vector. Всё-таки std::stack — это не урезанная версия std::vector, и было бы логично реализовать структуру с меньшим функционалом оптимальнее, чем со сложным.
(Правда, это урезанная версия std::deque...)
Лол. Что там убеждать-то, и так видно.
http://mirror.codeforces.com/contest/490/submission/8894056 http://mirror.codeforces.com/contest/490/submission/8894061
Разница только в параметрах шаблона стека в дереве фенвика. По умолчанию при чем там deque, если не указать иное.
P.S. На segment_tree_t не смотри, он с прошлых посылок остался, с ним даже со вектором внутри стека не заходит.
Было бы логично, но так не делают.
Сравнение не совсем корректно.
std::stack не контейнер, а адаптер. Стандартные контейнеры это std::list, std::vector и std::deque. "Под капотом" у стека всегда есть какой-то контейнер, по умолчанию в g++ это deque.
То есть по сути сравнивая stack и vector ты сравниваешь deque (при условии того, что его пользуют как стек) и vector (при тех же условиях).
В чём же заключается сложность функционала std::vector?
Если нужны только операции взятия и удаления, то лучше использовать стек, ИМХО
Вектор только если нужны еще какие-либо функции
где эта задача находится на онлайн ресурсе
"Чистую" задачу я не нашёл, но вот эта задача сводится к поиску максимальной подматрицы.
Вот похожая задача на топкодере: ссылка
сайт contest.bsuir.by там [Practice. Dynamic programming] problem I
сайт [practice.Dynamic programming], задача I.мистер средний
ACMP — фермер 2
вот, спасибо, когда-то решал эту задачу, вспоминал о ней, но не мог найти ее и своего решения. Но решал я эту задачу и совсем не так, как написано на е-максе, а так: линк. Но думаю, для прямоугольников такой метод не прокатит.
Хотя если хранить в каждой клетке динамики 2 стороны прямоугольника, то наверное может пройти.