Изменения

{{Шаблон: Задача|definition = Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}{{Определение|definition = '''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''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² &#215; m⁴²)==Построим следующую динамику: <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] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d[][] </tex> уже известны, тогда очередное значение <texdpi="130"> d[i][j] = \max(d[k][l] + 1, </tex> для всех <tex> \limits_{k = 1..i-1 </tex> и <tex> \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>.

'''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m] d[n][m] //динамика prev[n] //массив предков inputData(a, n''') inputData(b, m) '''for ''' i = 1...'''to''' n '''for ''' j = 1...'''to''' m '''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_i, b_j) b_j := 1 //d[b_i][b_j] <tex> \rightarrow </tex> max '''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 print(d[ pos = b_i][b_j]) //размер НОВП pos : <font color= b_i green>//проходим по массиву a, выписывая элементы НОВП</font> answer: '''vector<int>''' '''while ''' pos != <tex> \neq </tex> 0: print answer.pushBack(a[pos]) pos := prev[pos] '''return''' answer

==Решение за время O(N³)==Улучшим предыдущее решение. Пусть теперь <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-1m] </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> j-1 </tex> в <tex> d[k][j-1] </tex>, то есть без элемента <tex> b[j] </tex>. Но так как последовательность ''строго возрастает'', <tex> b[j] </tex> точно не будет два раза элементом НОВП. Тогда мы, не рассматривая граничные случаи <tex> d[i][0] </tex>, можем использовать индекс <tex> j </tex> и в динамике <tex> d[k][j] </tex>предыдущем решении.

'''vector<texint> d''' LCIS(a: '''int[n]''', b: '''int[m]''') '''for''' i = 1 '''to''' n '''for''' j = 1 '''to''' m '''if''' a[i]== b[j] = max( d[ki][j]) + = 1 <font color=green>/tex/ НОВП как минимум 1, состоит из одного элемента a[i] <-> для всех b[j]<tex/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 <font color=green>// проходим по массиву a, выписывая элементы НОВП</font> answer: '''vector<int>''' '''while''' pos <tex> \neq </tex>0 answer.pushBack(a[pos]) pos = prev[pos] '''return''' answer

for ==Решение за время O(n &#215; 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>.n Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта: for *<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j ] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.m if *<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] </НОВП как минимум 1tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, состоит из одного элемента что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[j] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex> '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[jm]''') '''for''' i = 1 '''to''' n ind = 0 <font color=green>// позиция "лучшего" элемента в массиве b</font> best = 0 <font color=green>// значение динамики для "лучшего" элемента</font> '''for k ''' j = 1 '''to''' m d[i][j] = d[i - 1][j] <font color= green>// НОВП на a[1...i-1 if ] и b[1..j] (без элемента a[ki] )< /font> '''if''' a[i] == b[j] '''and ''' d[i- 1][j] < best + 1 <font color=green>// используем a[i]-й элемент для увеличения НОВП</font> d[ki][j] = best + 1: prev[j] = ind d '''if''' a[i]> b[j] := '''and''' d[ki - 1][j] + 1 prev> best <font color=green>// при следующем равенстве a[i] := k= b[j']</font> else: best = d[i- 1][j] <font color= dgreen>// в best будет храниться "лучший" элемент</font> ind = j <font color=green>// b[iind]< b[j'] и d[i-1][ind] <tex> \rightarrow </tex> max</font> <font color=green>//восстановление(по массиву b)</font> b_i : pos = 1 <font color=green>//ищем лучший элемент d[b_in][mpos] <tex> \rightarrow </tex> max</font> '''for i ''' j = 1...n'''to''' m '''if ''' d[b_in][mpos] < d[in][mj]: b_i :pos = ij print(d[b_i][m]) //размер НОВП pos : <font color= b_i green>//проходим по массиву ab, выписывая элементы НОВП</font> answer: '''vector<int>''' '''while ''' pos != <tex> \neq </tex> 0: print answer.pushBack(ab[pos]) pos := prev[pos] '''return''' answer

==Решение за время O(N= Доказательство оптимальности ===В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма {{---}} это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <suptex>2d[i][j] </suptex>)==мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Пусть теперь Напомним, как обозначается динамика: <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> da[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> da[ki]</tex> и <tex> b[j] </tex> на префиксе {{---}} последние элементы НОВП префиксов <tex> a[1..ki] </tex> и <tex> b[1..j] </tex> была наилучшей: <tex> b[j] </tex> {{---}} по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. А раз мы считаем Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> da[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> и значение динамики для него максимально. Фактически, это решение отличается от предыдущих только более "хитрой" реализацией.

d[n][m] prev[m] for i = 1= См...n best_ind :также = 0 //позиция "лучшего" элемента в массиве b best := 0 //значение динамики для "лучшего" элемента for j = 1...m d*[i][j] := d[i-1Задача о наибольшей общей подпоследовательности][j] //НОВП на префиксе a*[1..i-1] и b[1..jЗадача о наибольшей возрастающей подпоследовательности], то есть без элемента a[i] if a[i] ==Источники информации = b[j] and d[i-1][j] < best + 1: //можем использовать a[i]-тый элемент для увеличения НОВП d[i][j] := best + 1 p[j] := best_ind if a[i] > b[j] and d[i-1][j] > best) //в момент следующего равенства a* [i] = b[j'] нам не придётся бежать циклом в поисках элемента khttp: best := d[i-1][j] //b[k] < b[j'] = a[i]codeforces. Мы считаем элемент a[i] фиксированным и сравниваем кандидатов с ним best_ind := j ru/contest/восстановление (по массиву b) b_j := 1 10/problem/ищем лучший элемент d[b_iD Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности][m] <tex> \rightarrow </tex> max for k = 1...m if d[n[Категория:Дискретная математика и алгоритмы]][b_j] < d[nКатегория:Динамическое программирование][j]: b_j := j print(d[n][b_j]) //размер НОВП pos := b_j //проходим по массиву b, выписывая элементы НОВП while pos != 0Категория: print(b[posДругие задачи динамического программирования]) pos := prev[pos]