19
правок
Изменения
м
vector<int> [] '''LCIS'''(vector<int> a, vector<int> b) d = : int[n][m] prev = , b: int[n]) '''for''' i = 1...'''to''' n '''for''' j = 1...'''to''' m
vector<int> answerpos = b_i pos <font color= b_i green>// проходим по массиву a, выписывая элементы НОВП</font> '''while''' pos != <tex> \neq </tex> 0 answer.pushpushBack(a[pos])
vector<int> [] '''LCIS'''(vector<int> a, vector<int> b) d = : int[n][m] prev = , b: int[n]) '''for''' i = 1...'''to''' n '''for''' j = 1...'''to''' m
vector<intfont color=green>// проходим по массиву a, выписывая элементы НОВП</font> answer '''while''' pos != <tex> \neq </tex> 0 answer.pushpushBack(a[pos])
vector<int> [] '''LCIS'''(vector<int> a, vector<int> b) d = : int[n][m] // динамика prev = , b: int[n] // массив предков ) '''for''' i = 1...'''to''' n ind = 0 <font color=green>// позиция "лучшего" элемента в массиве b</font> best = 0 <font color=green>// значение динамики для "лучшего" элемента</font> '''for''' j = 1...'''to''' m d[i][j] = d[i-1][j] <font color=green>// НОВП на a[1..i-1] и b[1..j] (без элемента a[i])</font> '''if''' a[i] == b[j] '''and''' d[i-1][j] < best + 1 <font color=green>// используем a[i]-й элемент для увеличения НОВП</font>
vector<intfont color=green>// проходим по массиву b, выписывая элементы НОВП</font> answer '''while''' pos != <tex> \neq </tex> 0 // проходим по массиву b, выписывая элементы НОВП answer.pushpushBack(b[pos])
Отформатировал псевдокод; заменил дефисы на тире; не нашёл терминов, нуждающихся в английском эквиваленте
==Решение за время O(N<sup>4</sup>)==
Построим следующую динамику: <tex> d[i][j] </tex> {{- --}} это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)
Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex dpi="130"> d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 </tex> при условии, что <tex> a[k] = b[l]. </tex>
Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{- --}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
'''if''' a[i] == b[j]
d[i][j] = 1 <font color=green> // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]</font> '''for''' k = 1...'''to''' i-1 '''for''' l = 1...'''to''' j-1
'''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
d[i][j] = d[k][l] + 1
prev[i] = k
<font color=green>//восстановление</font>
b_i = 1
b_j = 1
'''for''' i = 1...'''to''' n '''for''' j = 1...'''to''' m
'''if''' d[b_i][b_j] < d[i][j]
b_i = i
b_j = j
pos = prev[pos]
'''return''' answer
==Решение за время O(N<sup>3</sup>)==
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> {{- --}} динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>:
*Если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> {{- --}} максимальна.
<tex dpi="120"> d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 </tex> при условии, что <tex> a[k] < a[i].</tex>
Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.
'''if''' a[i] == b[j]
d[i][j] = 1 <font color=green>// НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]</font> '''for''' k = 1...'''to''' i-1
'''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
d[i][j] = d[k][j] + 1
prev[i] = k
'''else'''
d[i][j] = d[i][j-1] <font color=green>// восстановление</font> pos = 1 <font color=green>// ищем элемент c максимальным d[pos][m]</font> '''for''' i = 1...'''to''' n
'''if''' d[pos][m] < d[i][m]
pos = i
pos = prev[pos]
'''return''' answer
==Решение за время O(N<sup>2</sup>)==
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> {{- --}} это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> {{--- }} последний представитель НОВП массива <tex> b </tex>, а <tex> a[i] </tex> может не быть последним в массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве {{--- }} по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> b[k] < b[j] </tex> с наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[k] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex>
d[i][j] = best + 1
prev[j] = ind
'''if''' a[i] > b[j] '''and''' d[i-1][j] > best <font color=green>// при следующем равенстве a[i] == b[j']</font> best = d[i-1][j] <font color=green>// в best будет храниться "лучший" элемент: </font> ind = j <font color=green>// b[ind] < b[j'] и d[i][ind] <tex> \rightarrow </tex> max</font> <font color=green>// восстановление (по массиву b)</font> pos = 1 <font color=green>// ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max</font> '''for''' j = 1...'''to''' m
'''if''' d[n][pos] < d[n][j]
pos = j
pos = prev[pos]
'''return''' answer
=== Доказательство оптимальности ===
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма {{- --}} это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Напомним, как обозначается динамика: <tex> d[i][j] </tex> {{--- }} это НОВП на префиксах <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, где последним элементом НОВП является элемент <tex> b[j] </tex>, а <tex> a[i] </tex> может не быть равен <tex> b[j] </tex> (то есть элемент <tex> a[i'] = b[j] </tex> лежит где-то в префиксе <tex> a[1..i] </tex>). Итак, для <tex> d[i][j] </tex> есть два варианта:
* <tex> a[i] \neq b[j] </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] </tex> лежит в <tex> a[1..i-1] </tex>.
* <tex> a[i] = b[j] </tex>, тогда <tex> a[i] </tex> и <tex> b[j] </tex> {{- --}} последние элементы НОВП префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>: <tex> b[j] </tex> {{--- }} по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> a[k] = b[j] </tex>, то его можно заменить на элемент <tex> a[i] </tex> без уменьшения длины НОВП. Если же в <tex> a[1..i-1] </tex> такого элемента нет, то <tex> a[i] </tex> {{--- }} единственный из возможных вариантов. Итак, <tex> a[i] </tex> и <tex> b[j] </tex> {{--- }} последние элементы НОВП. Значит, начало НОВП (<tex> d[i][j] </tex>) лежит в префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j-1] </tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[k] < b[j] </tex> с лучшей динамикой <tex> d[i-1][k] </tex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе <tex> a[1..i-1] </tex>.
== См. также ==
