Просмотр исходного текста страницы Задача о наибольшей общей возрастающей последовательности

{{Шаблон: Задача
|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(n<sup>2</sup> &#215; 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> уже известны, тогда очередное значение <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>.

 '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[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_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 = b_i 
   <font color=green>// проходим по массиву a, выписывая элементы НОВП</font>
   answer: '''vector<int>'''
   '''while''' pos <tex> \neq </tex> 0
     answer.pushBack(a[pos])
     pos = prev[pos]
   '''return''' answer

==Решение за время O(n<sup>2</sup> &#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 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>, как и в предыдущем решении.

 '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[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
           '''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

==Решение за время 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>. Тогда для очередного значения <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[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

=== Доказательство оптимальности ===
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <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>.

== См. также ==

*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]

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

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Другие задачи динамического программирования]]