19
правок
Изменения
м
'''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
Исправил замечания
{{Определение
|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(N<sup>4</sup>)==
Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
'''int[] '''LCIS(a: '''(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>
<font color=green>// восстановление</font>
b_i = 1
Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.
'''int[] '''LCIS(a: '''(a: int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' m
*<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>
'''int[] '''LCIS(a: '''(a: int[n]''', b: '''int[m]''')
'''for''' i = 1 '''to''' n
ind = 0 <font color=green>// позиция "лучшего" элемента в массиве b</font>
== Источники информации ==
* [http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Другие задачи]]
