Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 146 |
| 3 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
быть может это поможет Вам: 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 стороны прямоугольника, то наверное может пройти.