Изменения

{{Шаблон: Задача|definition = Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}

'''Наибольшая общая возрастающая подпоследовательность (, НОВП)''' (''англ. ''. 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 < \dots 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> 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: '''(vector<int> a[n]''', vector<int> b) d = : '''int[n][m] // динамика prev = int[n] // массив предков''') '''for''' i = 1...'''to''' n '''for''' j = 1...'''to''' m

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

vector<int> answerpos = b_i pos <font color= b_i green>// проходим по массиву a, выписывая элементы НОВП</font> answer: '''vector<int>''' '''while''' pos != <tex> \neq </tex> 0 answer.pushpushBack(a[pos])

==Решение за время O(Nn³²&#215; 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> 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>}} максимальна.

<texdpi="120"> d[i][j] = \max(\limits_{k = 1..i-1} d[k][j]) + 1 </tex> для всех при условии, что <tex> k = 1..i-1, a[k] < a[i]). </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

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

d[i][j] = d[i][j-1] <font color=green>//восстановление</font> b_i : pos = 1 <font color=green>//ищем лучший элемент c максимальным d[b_ipos][m] <tex> \rightarrow </texfont> max '''for''' i = 1...'''to''' n '''if''' d[b_ipos][m] < d[i][m] b_i :pos = i print(d[b_i][m]) //размер НОВП 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²n &#215; m)==Пусть теперь Модифицируем предыдущее решение, добавив небольшую ''хитрость''. Теперь <tex> d[i][j] </tex> {{--- }} это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex> (элементы , причем элемент <tex> ab[ij] </tex> и {{---}} последний представитель НОВП массива <tex> b</tex>, а <tex> a[ji] </tex> могут может не входить быть последним в НОВП)массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве {{--- }} по увеличению <tex> j </tex>. Заметим, что в предыдущем решении при каждом равенстве элементов Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:*<tex> a[i] </tex> и не входит в НОВП. Тогда <tex> bd[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[ki][j] </tex> на префиксе нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> ab[1..k] < b[j] </tex> и с наибольшим значением <tex> bd[i-1..j][k] </tex> была наилучшей. А раз Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex> , то поэтому будем считать <tex> a[i] </tex> можно считать ''фиксированным, а ''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[jk] </tex> - переменным. Тогда давайте , в дополнительной переменной <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[m]''') '''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> 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-1][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 <font color=green>// проходим по массиву b, выписывая элементы НОВП</font> answer: '''vector<int>''' '''while''' pos <tex> \neq </tex> 0 answer.pushBack(b[pos]) pos = prev[pos] '''return''' answer

d[n][m]=== Доказательство оптимальности === prevВ данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[mi] '''for''' i = 1...n best_ind := 0 //позиция "лучшего" элемента в массиве b best := 0 [j] <//значение динамики tex> не влияет на корректность алгоритма {{---}} это всего лишь уловки реализации. Поэтому покажем, что для "лучшего" элемента '''for''' j = 1...m вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Напомним, как обозначается динамика:= <tex> d[i-1][j] /</tex> {{---}} это НОВП на префиксе префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j]</tex>, то есть без элемента aгде последним элементом НОВП является элемент <tex> b[ij] '''if''' </tex>, а <tex> a[i] == </tex> может не быть равен <tex> b[j] '''and''' d</tex> (то есть элемент <tex> a[i-1']= b[j] < best + 1 //можем использовать tex> лежит где-то в префиксе <tex> a[1..i]-тый элемент </tex>). Итак, для увеличения НОВП <tex> d[i][j] </tex> есть два варианта:= best + 1 p* <tex> a[i] \neq b[j] := best_ind '''if''' </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] '''and''' d</tex> лежит в <tex> a[1..i-1]</tex>.* <tex> a[i] = b[j] </tex> best , тогда <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> как элемент, который может стать последним, не придётся бежать циклом ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в поисках элемента k: best := dпрефиксе <tex> a[1..i-1]</tex> есть элемент <tex> a[k] = b[j] <//btex>, то его можно заменить на элемент <tex> a[ki] < b/tex> без уменьшения длины НОВП. Если же в <tex> a[j'1..i-1] = </tex> такого элемента нет, то <tex> a[i]</tex> {{---}} единственный из возможных вариантов. Мы считаем элемент Итак, <tex> a[i] фиксированным </tex> и сравниваем кандидатов с ним best_ind := <tex> b[j ] <//восстановление tex> {{---}} последние элементы НОВП. Значит, начало НОВП (по массиву b) b_j := 1 //ищем лучший элемент <tex> d[ni][b_jj]</tex> \rightarrow ) лежит в префиксах </tex> max '''for''' k = a[1...m '''if''' d[ni-1]</tex> и <tex> b[b_j1..j-1] < d/tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[nk]< b[j] b_j := j print(</tex> с лучшей динамикой <tex> d[ni-1][b_jk]) <//размер НОВП pos := b_j //проходим по массиву btex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, выписывая элементы что конец такой НОВП '''while''' pos != 0 print(bлежит в префиксе <tex> a[pos]) pos := prev[pos1..i-1]</tex>.

== Источники информации ==

*[http://codeforces.ru/contest/10/problem/D Codeforces {{- --}} Задача о наибольшей общей возрастающей подпоследовательности]