e-maxx_algo

Нахождение наидлиннейшей возрастающей подпоследовательности

этой последовательности строго возрастающую подпоследовательность наибольшей длины.

Формально это выглядит следующим образом: требуется найти такую последовательность индексов , что:

В данной статье рассматриваются различные алгоритмы решения данной задачи, а также некоторые задачи, которые можно свести к данной задаче.

Решение за : метод динамического программирования

Динамическое программирование — это весьма общая методика, позволяющая решать огромный класс задач. Здесь мы рассмотрим эту методику применительно к нашей конкретной задаче.

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

Динамическое программирование для поиска длины ответа

Для этого давайте научимся считать массив , где — это длина наидлиннейшей возрастающей подпоследовательности, оканчивающейся именно в элементе с индексом . Массив этот (он и есть —

уже подсчитаны. Тогда заметим, что у нас есть два варианта:

Объединяя эти два варианта в один, получаем окончательный алгоритм для вычисления :

Этот алгоритм — и есть сама динамика.

Реализация

Приведём реализацию описанного выше алгоритма, которая находит и выводит длину наидлиннейшей возрастающей подпоследовательности:

int d[MAXN]; // константа MAXN равна наибольшему возможному значению n

for (int i=0; i<n; ++i) { d[i] = 1;

for (int j=0; j<i; ++j) if (a[j] < a[i])

d[i] = max (d[i], 1 + d[j]);

}

с двоичным поиском

возрастающая подпоследовательность длины (а если таких чисел несколько — то наименьшее из них). Изначально мы полагаем , а все остальные элементы .

Считать эту динамику мы будем постепенно, обработав число , затем , и т.д. Приведём реализацию этой динамики за :

int d[MAXN]; d[0] = -INF;

for (int i=1; i<=n; ++i) d[i] = INF;

for (int i=0; i<n; i++)

for (int j=1; j<=n; j++)

if (d[j-1] < a[i] && a[i] < d[j]) d[j] = a[i];

Реализация за

Воспользовавшись стандартным в языке C++ алгоритмом двоичного поиска (который возвращает позицию первого элемента, строго большего данного), получаем такую простую реализацию:

int d[MAXN]; d[0] = -INF;

for (int i=1; i<=n; ++i) d[i] = INF;

for (int i=0; i<n; i++) {

int j = int (upper_bound (d.begin(), d.end(), a[i]) - d.begin()); if (d[j-1] < a[i] && a[i] < d[j])

d[j] = a[i];

}

Восстановление ответа

По такой динамике тоже можно восстановить ответ, для чего опять же помимо динамики также надо хранить массив "предков" — то, на элементе с каким индексом оканчивается оптимальная подпоследовательность длины

который должен стоять перед в оптимальной подпоследовательности.

Поддерживая эти два массива по ходу вычисления динамики, в конце будет нетрудно восстановить искомую подпоследовательность.

(Интересно отметить, что применительно к данной динамике ответ можно восстанавливать только так, через массивы предков — а без них восстановить ответ после вычисления динамики будет невозможно. Это один из редких случаев, когда к динамике неприменим альтернативный способ восстановления — без массивов предков).

Решение за : структуры данных

другой путь: воспользоваться одной из известных простых структур данных.

В самом деле, давайте вернёмся к самой первой динамике, где состоянием являлась просто текущая позиция.

Следовательно, если мы через обозначим такой массив, в который будем записывать значения динамики от чисел:

то получается, что всё, что нам надо уметь — это искать максимум на префиксе массива

: .

Задача поиска максимума на префиксах массива (с учётом того, что массив может меняться) решается многими стандартными структурами данных, например, деревом отрезков или деревом Фенвика.

Воспользовавшись любой такой структурой данных, мы получим решение за .

У этого способа решения есть явные недостатки: по длине и сложности реализации этот путь будет в любом случае хуже, чем описанная выше динамика за . Кроме того, если входные числа могут

быть достаточно большими, то скорее всего их придётся сжимать (т.е. перенумеровывать от до ) — без этого многие стандартные структуры данных работать не смогут из-за высокого потребления памяти.

С другой стороны, у данного пути есть и преимущества. Во-первых, при таком способе решения не придётся задумываться о хитрой динамике. Во-вторых, этот способ позволяет решать некоторые обобщения нашей задачи (о них см. ниже).

Смежные задачи

Приведём здесь несколько задач, тесно связанных с задачей поиска наидлиннейшей возрастающей подпоследовательности.

Наидлиннейшая неубывающая подпоследовательность

Фактически, это та же самая задача, только теперь в искомой подпоследовательности допускаются одинаковые числа (т. е. мы должны найти нестрого возрастающую подпоследовательность).

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

Количество наидлиннейших возрастающих подпоследовательностей

По всей видимости, способ решения через динамику за к данной задаче применить невозможно.

Наименьшее число невозрастающих подпоследовательностей, покрывающих данную

число цветов так, чтобы по каждому цвету получалась бы невозрастающая подпоследовательность.

Решение. Утверждается, что минимальное количество необходимых цветов равно длине наидлиннейшей возрастающей подпоследовательности.

Доказательство. Фактически, нам надо доказать двойственность этой задачи и задачи поиска наидлиннейшей возрастающей подпоследовательности. Обозначим через длину наидлиннейшей возрастающей подпоследовательности, а через — искомое наименьшее число невозрастающих подпоследовательностей. Нам надо доказать, что .

набор таким образом: пока есть две таких подпоследовательности, что первая начинается раньше второй, но при этом первая начинается с числа, больше либо равного чем начало второй — отцепим это стартовое число от первой подпоследовательности и прицепим в начало второй. Таким образом, через какое-то конечное число шагов у нас останется подпоследовательностей, причём их стартовые числа будут образовывать

Таким образом, в самом деле, , что и требовалось доказать.

Восстановление ответа. Утверждается, что само искомое разбиение на подпоследовательности можно искать жадно, т.е. идя слева направо и относя текущее число в ту подпоследовательность, которая сейчас заканчивается на минимальное число, больше либо равное текущему.

Динамика по профилю. Задача "паркет"

Типичными задачами на динамику по профилю, являются:

●найти количество способов замощения поля некоторыми фигурами

●найти замощение с наименьшим количеством фигур

●найти замощение с минимальным количеством неиспользованных клеток

●найти замощение с минимальным количеством фигур такое, что в него нельзя добавить ещё одну фигуру

Задача "Паркет"

Имеется прямоугольная площадь размером NxM. Нужно найти количество способов замостить эту площадь фигурами 1x2 (пустых клеток не должно оставаться, фигуры не должны накладываться друг на друга).

Построим такую динамику: D[I][Mask], где I=1..N, Mask=0..2^M-1. I обозначает количество строк в текущем поле, а Mask - профиль последней строки в текущем поле. Если j-й бит в Mask равен нулю, то в этом месте профиль проходит

на "нормальном уровне", а если 1 - то здесь "выемка" глубиной 1. Ответом, очевидно, будет D[N][0].

Строить такую динамику будем, просто перебирая все I=1..N, все маски Mask=0..2^M-1, и для каждой маски будем делать переходы вперёд, т.е. добавлять к ней новую фигуру всеми возможными способами.

Реализация:

int n, m;

vector < vector<long long> > d;

void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)

{

if (x == n) return;

if (y >= m)

d[x+1][next_mask] += d[x][mask];

else

{

int my_mask = 1 << y; if (mask & my_mask)

calc (x, y+1, mask, next_mask);

else

{

calc (x, y+1, mask, next_mask | my_mask);

if (y+1 < m && ! (mask & my_mask) && ! (mask &

(my_mask << 1)))

calc (x, y+2, mask, next_mask);

}

}

}

int main()

{

cin >> n >> m;

d.resize (n+1, vector<long long> (1<<m)); d[0][0] = 1;

for (int x=0; x<n; ++x)

for (int mask=0; mask<(1<<m); ++mask) calc (x, 0, mask, 0);

cout << d[n][0];

}

Нахождение наибольшей нулевой подматрицы

Дана матрица размером . Требуется найти в ней такую подматрицу, состоящую только из нулей, и среди всех таких — имеющую наибольшую площадь (подматрица — это прямоугольная область матрицы).

Тривиальный алгоритм, — перебирающий искомую подматрицу, — даже при самой хорошей реализации будет

Алгоритм

Шаг 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;

Метод Гаусса решения системы линейных уравнений

Дана система линейных алгебраических уравнений (СЛАУ) с неизвестными. Требуется решить эту систему: определить, сколько решений она имеет (ни одного, одно или бесконечно много), а если она имеет хотя бы одно решение, то найти любое из них.

Формально задача ставится следующим образом: решить систему:

Удобно матричное представление этой задачи:

где — матрица , составленная из коэффициентов , и — векторы-столбцы высоты .

Стоит отметить, что СЛАУ может быть не над полем действительных чисел, а над полем по модулю какоголибо числа , т.е.:

— алгоритм Гаусса работает и для таких систем тоже (но этот случай будет рассмотрен ниже в отдельном разделе).

Алгоритм Гаусса

Строго говоря, описываемый ниже метод правильно называть методом "Гаусса-Жордана" (Gauss-Jordan

elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г. (стоит отметить, что Вильгельм Жордан не является автором ни теоремы Жордана о кривых, ни жордановой алгебры

— всё это три разных учёных-однофамильца; кроме того, по всей видимости, более правильной является транскрипция "Йордан", но написание "Жордан" уже закрепилось в русской литературе). Также интересно заметить,

что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).

Базовая схема

Кратко говоря, алгоритм заключается в последовательном исключении переменных из каждого уравнения до тех пор, пока в каждом уравнении не останется только по одной переменной. Если , то можно говорить, что алгоритм Гаусса-Жордана стремится привести матрицу системы к единичной матрице — ведь после того как матрица стала единичной, решение системы очевидно — решение единственно и задаётся получившимися коэффициентами .

При этом алгоритм основывается на двух простых эквивалентных преобразованиях системы: во-первых, можно обменивать два уравнения, а во-вторых, любое уравнение можно заменить линейной комбинацией этой строки (с ненулевым коэффициентом) и других строк (с произвольными коэффициентами).

На первом шаге алгоритм Гаусса-Жордана делит первую строку на коэффициент . Затем алгоритм прибавляет первую строку к остальным строкам с такими коэффициентами, чтобы их коэффициенты в первом столбце обращались в нули — для этого, очевидно, при прибавлении первой строки к -ой надо домножать её на . При каждой операции с матрицей (деление на число, прибавление к одной строке другой) соответствующие операции производятся и с вектором ; в некотором смысле, он ведёт себя, как если бы он был -ым столбцом матрицы .

В итоге, по окончании первого шага первый столбец матрицы станет единичным (т.е. будет содержать единицу в первой строке и нули в остальных).

Аналогично производится второй шаг алгоритма, только теперь рассматривается второй столбец и вторая строка: сначала вторая строка делится на , а затем отнимается от всех остальных строк с такими коэффициентами,