202
правки
Изменения
Нет описания правки
{{Шаблон: Задача|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 < \dots 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 </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: '''(vector<int> a[n]''', vector<int> b) d = : '''int[n][m] // динамика''') prev = int[n] // массив предков '''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
Длина НОВП будет в элементе с максимальным значением <tex> d[i][jm] = max(d[k][j]) + 1 </tex> для всех . Для восстановления ответа будем хранить массив предков по массиву <tex> k = 1..i-1, a[k] < a[i]). </tex>, как и в предыдущем решении.
'''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''') '''for''' i = 1...'''to''' n '''for''' j = 1...'''to''' m
'''if''' a[i] == b[j]
'''else'''
==Решение за время O(N<sup>2</sup>n × 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[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> 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][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
== См. также ==
*[[Задача о наибольшей возрастающей подпоследовательности]]
== Источники информации ==
*[http://codeforces.ru/contest/10/problem/D Codeforces {{- --}} Задача о наибольшей общей возрастающей подпоследовательности]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Другие задачи динамического программирования]]