Задача о наибольшей общей возрастающей последовательности — различия между версиями
(→Решение за время O(N3)) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 44 промежуточные версии 6 участников) | |||
Строка 1: | Строка 1: | ||
− | Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).'' | + | {{Шаблон: Задача |
+ | |definition = | ||
+ | Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}} | ||
{{Определение | {{Определение | ||
|definition = | |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( | + | ==Решение за время O(n<sup>2</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[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> 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] \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> d[i][j] = max | + | *Если <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> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>. | + | Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>. |
− | vector<int> '''LCIS''' | + | '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''') |
− | + | '''for''' i = 1 '''to''' n | |
− | + | '''for''' j = 1 '''to''' m | |
− | '''for''' i = 1 | ||
− | '''for''' j = 1 | ||
'''if''' a[i] == b[j] | '''if''' a[i] == b[j] | ||
− | d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента 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 = 1 |
− | b_j = 1 | + | b_j = 1 |
− | '''for''' i = 1 | + | '''for''' i = 1 '''to''' n |
− | '''for''' j = 1 | + | '''for''' j = 1 '''to''' m |
'''if''' d[b_i][b_j] < d[i][j] | '''if''' d[b_i][b_j] < d[i][j] | ||
b_i = i | b_i = i | ||
b_j = j | b_j = j | ||
− | + | pos = b_i | |
− | + | <font color=green>// проходим по массиву a, выписывая элементы НОВП</font> | |
− | '''while''' pos | + | answer: '''vector<int>''' |
− | answer. | + | '''while''' pos <tex> \neq </tex> 0 |
+ | answer.pushBack(a[pos]) | ||
pos = prev[pos] | pos = prev[pos] | ||
'''return''' answer | '''return''' answer | ||
− | ==Решение за время O( | + | ==Решение за время O(n<sup>2</sup> × m)== |
− | Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> - динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex> | + | Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> {{---}} динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>: |
− | Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </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][ | + | Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении. |
− | vector<int> '''LCIS''' | + | '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''') |
− | + | '''for''' i = 1 '''to''' n | |
− | + | '''for''' j = 1 '''to''' m | |
− | '''for''' i = 1 | ||
− | '''for''' j = 1 | ||
'''if''' a[i] == b[j] | '''if''' a[i] == b[j] | ||
− | d[i][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''' | '''else''' | ||
− | d[i][j] = d[i][j-1] | + | d[i][j] = d[i][j - 1] |
− | // восстановление | + | <font color=green>// восстановление</font> |
− | + | pos = 1 <font color=green>// ищем элемент c максимальным d[pos][m]</font> | |
− | '''for''' i = 1 | + | '''for''' i = 1 '''to''' n |
− | '''if''' d[ | + | '''if''' d[pos][m] < d[i][m] |
− | + | pos = i | |
− | + | <font color=green>// проходим по массиву a, выписывая элементы НОВП</font> | |
− | + | answer: '''vector<int>''' | |
− | '''while''' pos | + | '''while''' pos <tex> \neq </tex> 0 |
− | answer. | + | answer.pushBack(a[pos]) |
pos = prev[pos] | pos = prev[pos] | ||
'''return''' answer | '''return''' answer | ||
− | ==Решение за время O( | + | ==Решение за время O(n × 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>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== См. также == | == См. также == | ||
Строка 103: | Строка 113: | ||
*[[Задача о наибольшей возрастающей подпоследовательности]] | *[[Задача о наибольшей возрастающей подпоследовательности]] | ||
− | == Источники == | + | == Источники информации == |
− | *http://codeforces.ru/contest/10/problem/D Codeforces - Задача о наибольшей общей возрастающей подпоследовательности | + | * [http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности] |
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория:Динамическое программирование]] | [[Категория:Динамическое программирование]] | ||
+ | [[Категория:Другие задачи динамического программирования]] |
Текущая версия на 19:05, 4 сентября 2022
Задача: |
Даны два массива: | и . Требуется найти их наибольшую общую возрастающую подпоследовательность (НОВП).
Определение: |
Наибольшая общая возрастающая подпоследовательность, НОВП (англ. longest common increasing subsequence, LCIS) массива | длины и массива длины — это последовательность такая, что , является подпоследовательностью и .
Содержание
Решение за время O(n2 × m2)
Построим следующую динамику:
— это длина наибольшей возрастающей подпоследовательности массивов и , последний элемент которой и . Будем заполнять сначала по увеличению , а при равенстве по увеличению . Ответом на задачу будет максимум из всех элементов (где , )Заполнять
будем следующим образом: на очередном шаге сравниваем элементы и :- Если , то (так как нет НОВП, оканчивающейся в разных элементах).
- Если , то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах и . Заметим, что предыдущие значения уже известны, тогда очередное значение при условии, что
Длина НОВП будет в элементе с максимальным значением
. Для восстановления подпоследовательности можно хранить массив предков массива — индекс предыдущего элемента НОВП, которая оканчивается в .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 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
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
// восстановление
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
// проходим по массиву a, выписывая элементы НОВП
answer: vector<int>
while pos
0
answer.pushBack(a[pos])
pos = prev[pos]
return answer
Решение за время O(n2 × m)
Улучшим предыдущее решение. Пусть теперь
— динамика, в которой элемент по-прежнему последний представитель НОВП массива , а может не быть быть последним представителем массива :- Если , будем "протаскивать" последнее удачное сравнение в динамике: (понять это можно так: , поэтому не последний представитель НОВП из массива , а значит предыдущий элемент НОВП находится в префиксе , но уже посчитан).
- Если , то одним дополнительным циклом пробежим по и найдём предыдущий элемент НОВП, оканчивающейся в (он меньше ). Из подходящих элементов выберем тот, для которого — максимальна.
при условии, что
Длина НОВП будет в элементе с максимальным значением
. Для восстановления ответа будем хранить массив предков по массиву , как и в предыдущем решении.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 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
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]
// восстановление
pos = 1 // ищем элемент c максимальным d[pos][m]
for i = 1 to n
if d[pos][m] < d[i][m]
pos = i
// проходим по массиву a, выписывая элементы НОВП
answer: vector<int>
while pos
0
answer.pushBack(a[pos])
pos = prev[pos]
return answer
Решение за время O(n × m)
Модифицируем предыдущее решение, добавив небольшую хитрость. Теперь
— это длина наибольшей общей возрастающей подпоследовательности префиксов и , причем элемент — последний представитель НОВП массива , а может не быть последним в массиве . Вычислять будем всё так же: сначала по увеличению , а при равенстве — по увеличению . Тогда для очередного значения есть два варианта:- не входит в НОВП. Тогда : значение динамики уже посчитано на префиксе .
- входит в НОВП. Это значит, что , то есть для подсчёта нужно пробегать циклом по в поисках элемента с наибольшим значением . Но мы считаем сначала по увеличению , поэтому будем считать фиксированным. Чтобы не запускать цикл при каждом равенстве элементу , в дополнительной переменной будем хранить "лучший" элемент (и его индекс в массиве ) такой, что этот элемент строго меньше (а также меньше ) и значение динамики для него максимально: и
vector<int> LCIS(a: int[n], b: int[m]) for i = 1 to n ind = 0 // позиция "лучшего" элемента в массиве b best = 0 // значение динамики для "лучшего" элемента for j = 1 to 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 prev[j] = ind if a[i] > b[j] and d[i - 1][j] > best // при следующем равенстве a[i] == b[j'] best = d[i - 1][j] // в best будет храниться "лучший" элемент ind = j // b[ind] < b[j'] и d[i-1][ind]max // восстановление (по массиву b) pos = 1 // ищем лучший элемент d[n][pos] max for j = 1 to m if d[n][pos] < d[n][j] pos = j // проходим по массиву b, выписывая элементы НОВП answer: vector<int> while pos 0 answer.pushBack(b[pos]) pos = prev[pos] return answer
Доказательство оптимальности
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев
не влияет на корректность алгоритма — это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Напомним, как обозначается динамика: — это НОВП на префиксах и , где последним элементом НОВП является элемент , а может не быть равен (то есть элемент лежит где-то в префиксе ). Итак, для есть два варианта:- , тогда не влияет на результат, и последний элемент НОВП лежит в .
- , тогда и — последние элементы НОВП префиксов и : — по определению динамики, а как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе есть элемент , то его можно заменить на элемент без уменьшения длины НОВП. Если же в такого элемента нет, то — единственный из возможных вариантов. Итак, и — последние элементы НОВП. Значит, начало НОВП ( ) лежит в префиксах и (значения для которых уже посчитаны). Мы ищем элемент с лучшей динамикой , что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе .
См. также
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности