MAXimal | |
добавлено: 11 Jun 2008 11:09 Содержание [скрыть] Нахождение наибольшей нулевой подматрицыДана матрица размером . Требуется найти в ней такую подматрицу, состоящую только из нулей, и среди всех таких — имеющую наибольшую площадь (подматрица — это прямоугольная область матрицы). Тривиальный алгоритм, — перебирающий искомую подматрицу, — даже при самой хорошей реализации будет работать . Ниже описывается алгоритм, работающий за , т.е. за линейное относительно размеров матрицы время. АлгоритмДля устранения неоднозначностей сразу заметим, что равно числу строк матрицы , соответственно, — это число столбцов. Элементы матрицы будем нумеровать в -индексации, т.е. в обозначении индексы и пробегают диапазоны , . Шаг 1: Вспомогательная динамикаСначала посчитаем следующую вспомогательную динамику: — ближайшая сверху единица для элемента . Формально говоря, равно наибольшему номеру строки (среди строк диапазоне от до ), в которой в -ом столбце стоит единица. В частности, если такой строки нет, то полагается равным (это можно понимать как то, что вся матрица как будто ограничена снаружи единицами). Эту динамику легко считать двигаясь по матрице сверху вниз: пусть мы стоит в -ой строке, и известно значение динамики для предыдущей строки. Тогда достаточно скопировать эти значения в динамику для текущей строки, изменив только те элементы, в которых в матрице стоят единицы. Понятно, что тогда даже не требуется хранить всю прямоугольную матрицу динамики, а достаточно только одного массива размера : vector<int> d (m, -1); for (int i=0; i<n; ++i) { for (int j=0; j<m; ++j) if (a[i][j] == 1) d[j] = i; // вычислили d для i-ой строки, можем здесь использовать эти значения } Шаг 2: Решение задачиУже сейчас мы можем решить задачу за — просто перебирать в текущей строке номер левого и правого столбцов искомой подматрицы, и с помощью динамики вычислять за верхнюю границу нулевой подматрицы. Однако можно пойти дальше и значительно улучшить асимптотику решения. Ясно, что искомая нулевая подматрица ограничена со всех четырёх сторон какими-то единичками (либо границами поля), — которые и мешают ей увеличиться в размерах и улучшить ответ. Поэтому, утверждается, мы не пропустим ответ, если будем действовать следующим образом: сначала переберём номер нижней строки нулевой подматрицы, затем переберём, в каком столбце мы будем упирать вверх нулевую подматрицу. Пользуясь значением , мы сразу получаем номер верхней строки нулевой подматрицы. Осталось теперь определить оптимальные левую и правую границы нулевой подматрицы, — т.е. максимально раздвинуть эту подматрицу влево и вправо от -го столбца. Что значит раздвинуть максимально влево? Это значит найти такой индекс , для которого будет , и при этом — ближайший такой слева для индекса . Понятно, что тогда даёт номер левого столбца искомой нулевой подматрицы. Если такого индекса вообще нет, то положить (это означает, что мы смогли расширить текущую нулевую подматрицу влево до упора — до границы всей матрицы ). Симметрично можно определить индекс для правой границы: это ближайший справа от индекс такой, что (либо , если такого индекса нет). Итак, индексы и , если мы научимся эффективно их искать, дадут нам всю необходимую информацию о текущей нулевой подматрице. В частности, её площадь будет равна . Как же искать эти индексы и эффективно при фиксированных и ? Нас удовлетворит только асимптотика , хотя бы в среднем. Добиться такой асимптотики можно с помощью стека (stack) следующим образом. Научимся сначала искать индекс , и сохранять его значение для каждого индекса внутри текущей строки в динамике . Для этого будем просматривать все столбцы слева направо, и заведём такой стек, в котором всегда будут лежать только те столбцы, в которых значение динамики строго больше . Понятно, что при переходе от столбца к следующему столбцу требуется обновить содержимое этого стека. Утверждается, что требуется сначала положить в стек столбец (поскольку для него стек "хороший"), а затем, пока на вершине стека лежит неподходящий элемент (т.е. у которого значение ), — доставать этот элемент. Легко понять, что удалять из стека достаточно только из его вершины, и ни из каких других его мест (потому что стек будет содержать возрастающую по последовательность столбцов). Значение для каждого будет равно значению, лежащему в этот момент на вершине стека. Ясно, что поскольку добавлений в стек на каждой строчке происходит ровно штук, то и удалений также не могло быть больше, поэтому в сумме асимптотика будет линейной. Динамика для нахождения индексов считается аналогично, только надо просматривать столбцы справа налево. Также следует отметить, что этот алгоритм потребляет памяти (не считая входные данные — матрицу ). РеализацияЭта реализация вышеописанного алгоритма считывает размеры матрицы, затем саму матрицу (как последовательность чисел, разделённых пробелами или переводами строк), и затем выводит ответ — размер наибольшей нулевой подматрицы. Легко улучшить эту реализацию, чтобы она также выводила саму нулевую подматрицу: для этого надо при каждом изменении запоминать также номера строк и столбцов подматрицы (ими будут соответственно , , , ). int n, m; cin >> n >> m; vector < vector<int> > a (n, vector<int> (m)); for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) cin >> a[i][j]; int ans = 0; vector<int> d (m, -1), d1 (m), d2 (m); stack<int> st; for (int i=0; i<n; ++i) { for (int j=0; j<m; ++j) if (a[i][j] == 1) d[j] = i; while (!st.empty()) st.pop(); for (int j=0; j<m; ++j) { while (!st.empty() && d[st.top()] <= d[j]) st.pop(); d1[j] = st.empty() ? -1 : st.top(); st.push (j); } while (!st.empty()) st.pop(); for (int j=m-1; j>=0; --j) { while (!st.empty() && d[st.top()] <= d[j]) st.pop(); d2[j] = st.empty() ? m : st.top(); st.push (j); } for (int j=0; j<m; ++j) ans = max (ans, (i - d[j]) * (d2[j] - d1[j] - 1)); } cout << ans;
|