Это интересная и сложная задача динамического программирования: Codeforces 10D LCIS.
Описание проблемы длинное, вот упрощенный вариант:
Вам даны две последовательности целых чисел. Вам нужно найти их самую длинную общую возрастающую подпоследовательность (LCIS), то есть возрастающую последовательность максимальной длины, являющуюся подпоследовательностью обеих последовательностей.
Например:
sequence a: 2 3 1 6 5 4 6 sequence b: 1 3 5 6 LCIS of a and b: 3 5 6 sequence a: 1 2 0 2 1 sequence b: 1 0 1 LCIS of a and b: 0 1
Почему это интересно?
Я считаю, что люди, у которых есть определенные основы динамического программирования, решили эти две основные проблемы:
- LIS (самая длинная возрастающая подпоследовательность)
- LCS (самая длинная общая подпоследовательность)
Проблема заключается в запросе LCIS (самая длинная общая возрастающая подпоследовательность), что похоже на комбинацию проблем LIS и LCS.
Моя первоначальная идея заключалась в том, чтобы сначала найти LCS двух последовательностей, а затем найти LIS этой подпоследовательности. Однако это не удалось из-за следующего контрпримера:
sequence a: 3 2 1 4 sequence b: 3 4 2 1
LCS — 3 2 1, а LCIS — 3 4. Причина в том, что LCIS не обязательно входит в состав LCS.
Позже я еще подумал о том, можем ли мы сначала отдельно найти ЛИС каждой последовательности, а затем найти ЛСК этих двух ЛИС. Однако этот подход не работает, поскольку ЛИС каждой последовательности может иметь несколько решений. Нам нужно искать новый алгоритм.
Решение
В динамическом программировании проблемы, связанные с последовательностями, обычно можно рассматривать на основе текущего элемента, являющегося конечной точкой, например:
- В задаче LCS
f[i][j]представляет собой длину самой длинной общей подпоследовательности первой последовательности до i-го элемента и заканчиваяi, а второй последовательности до j-го элемента и заканчиваяj, уравнение перехода состояний выглядит следующим образом:
- В задаче LIS
f[i]представляет собой длину самой длинной возрастающей подпоследовательности, заканчивающейся i-м элементом среди первыхiэлементов. Уравнение перехода состояния выглядит следующим образом:
Для проблемы LCIS, если мы рассмотрим установку f[i][j] как длину LCIS, полученную путем выбора из первых i элементов последовательности a и первых j элементов последовательности b, аналогично LCS, но это не способствует переходу состояния.
Поэтому, исходя из идеи LIS, мы устанавливаем f[i][j] как длину LCIS, полученную путем выбора из первых i элементов последовательности a и заканчивающейся на b[j].
Есть два случая:
- Когда
a[i] != b[j], мы не можем выбратьa[i](поскольку LCIS заканчивается наb[j], необходимо выбратьb[j], поэтомуa[i]выбрать нельзя), т.е.:
- Когда
a[i] == b[j], мы перечисляем возможные подпоследовательности, заканчивающиеся наb[k](k < j), и проверяем, можем ли мы добавить в нихa[i](т. е.b[j]) (обратите внимание, что эта статья имеет индекс 1):
В целом, уравнение перехода состояния:
Тогда мы можем написать алгоритм O(n³):
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j])
{
for (int k = 1; k < j; k++)
if (b[k] < a[i])
f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
else
f[i][j] = f[i - 1][j];
В приведенном выше коде ключевой частью является цикл for(int k=1; k<j; k++).
Рассмотрим: последовательность a:[2, 3, 1, 7, 6] и последовательность b: [1, 4, 6, 6]
- Когда
i = 5, j = 3, a[5] = b[3],kпроходит от1до2, чтобы найти максимальноеf[i-1][k]. (Обратите внимание, что эта статья проиндексирована 1) - Когда
i = 5, j = 4, a[5] = b[4],kпроходит от1до3, чтобы найти максимальноеf[i-1][k], где цикл от1до2является повторяющимся обходом, как показано в зеленой области на рисунке 1, потому чтоa[5]не изменяется, а элементы, гдеb[k] < a[5]фиксируются, когдаkпроходит от1до2, и переход состояния не происходит:
На самом деле мы можем использовать переменную fmax для хранения максимального значения f[i-1][k] для первых j-1 элементов. Другими словами, мы сохраняем максимальное значение f[i-1][k] в зеленой области на рисунке 1. Таким образом мы можем устранить цикл для k.
Далее рассмотрим, как вывести путь для задачи DP. На самом деле путь к проблеме DP довольно прост. Нам просто нужно отслеживать переход каждого состояния, другими словами, записывать предыдущее состояние.
Код следующим образом:
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, m, a[N], b[N];
int f[N][N], pre[N][N];
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
cin >> m;
for (int j = 1; j <= m; ++j)
cin >> b[j];
/* O(n^3) solution
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(a[i] == b[j])
{
for(int k = 0; k < j; ++k)
if(a[i] > b[k])
f[i][j] = max(f[i][j], f[i-1][k]+1);
}
else f[i][j] = f[i-1][j];
}
*/
// O(n^2) solution
for (int i = 1; i <= n; ++i)
{
int fmax = 0, pos = 0;
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j]; // Exclude a[i] from LCIS
pre[i][j] = pre[i-1][j];
if (a[i] == b[j])
{ // Add a[i] to LCIS
// fmax is the maximum value of the O(n^3) solution f[i-1][k]+1
if (f[i][j] < fmax + 1)
{
f[i][j] = fmax + 1;
// Prepare for the output path, record the index of the
// previous element of the LCIS ending with b[j] among the
// first j elements of b, which is also an element of the
// first i elements of a.
pre[i][j] = pos;
}
}
if (b[j] < a[i])
{
if (f[i - 1][j] > fmax)
{
// fmax is the maximum value of the O(n^3) solution f[i-1][k]+1
fmax = f[i - 1][j];
pos = j;
}
}
}
}
int res = 0, last = 0, tot = 0, path[N];
// Looking for the length of LCIS and the position of the end of LCIS
for (int j = 1; j <= m; ++j)
{
if (res < f[n][j])
{
res = f[n][j];
last = j;
}
}
cout << res << endl;
int i = n, j = last;
// Using the pre-array, find the entire sequence step by step based on
// the last element of LCIS
while (i || j)
{
if (pre[i][j] != j)
path[++tot] = b[j];
j = pre[i][j];
i--;
}
while (tot)
cout << path[tot--] << ' ';
cout << endl;
return 0;
}
Заключение
В этой статье представлена интересная задача динамического программирования, которая, по-видимому, является комбинацией задач на самую длинную возрастающую подпоследовательность (LIS) и самую длинную общую подпоследовательность (LCS).
Однако, помимо заимствования идей из этих двух задач, у него есть существенные отличия, демонстрирующие разнообразный и сложный характер задач динамического программирования.
Динамическое программирование – это основной алгоритм компьютерных наук, требующий высокого уровня квалификации, многократной практики и способности применять его к различным задачам. В будущем будет представлено больше проблем с алгоритмами динамического программирования.
Наконец, если в этой статье есть какие-либо ошибки, просьба сообщить об этом. Спасибо.
