19
правок
Изменения
м
Исправил замечания
'''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''longest common increasing subsequence, LCIS'') массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, \ldots, x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \ldots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex>. }}
==Решение за время O(Nn<sup>42</sup> × m<sup>2</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[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
'''vector<int[]>''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
pos = b_i
<font color=green>// проходим по массиву a, выписывая элементы НОВП</font>
answer: '''vector<int>'''
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
'''return''' answer
==Решение за время O(Nn<sup>32</sup>× m)==
Улучшим предыдущее решение. Пусть теперь <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> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.
'''vector<int[]>''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
pos = i
<font color=green>// проходим по массиву a, выписывая элементы НОВП</font>
answer: '''vector<int>'''
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(a[pos])
'''return''' answer
==Решение за время O(N<sup>2</sup>n × m)==Модифицируем предыдущее решение, добавив небольшую "''хитрость"''. Теперь <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>
'''vector<int[]>''' LCIS(a: '''int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
ind = 0 <font color=green>// позиция "лучшего" элемента в массиве b</font>
pos = j
<font color=green>// проходим по массиву b, выписывая элементы НОВП</font>
answer: '''vector<int>'''
'''while''' pos <tex> \neq </tex> 0
answer.pushBack(b[pos])
