1765. Три последовательности

 

Даны три последовательности целых чисел. Найдите длину их наибольшей общей подпоследовательности.

 

Вход. Содержит описание трех последовательностей. Каждая последовательность задается в двух строках. Первая строка содержит длину последовательности n (1 ≤ n ≤ 100), а вторая – ее элементы (32-х битовые целые числа).

 

Выход. Выведите длину наибольшей общей подпоследовательности.

 

Пример входа

Пример выхода

 
3
1 2 3
3
1 3 2
3
2 1 3

2

 

 

РЕШЕНИЕ

динамическое программирование – НОП

 

Анализ алгоритма

Пусть a, b, c – три входные последовательности. Пусть f(i, j, k) равно длине НОП последовательностей a[1..i], b[1..j] и c[1..k]. Значение f(i, j, k) будем хранить в dp[i][j][k].

Если a[i] = b[j] = c[k], то

f(i, j, k) = 1 + f(i – 1, j – 1, k – 1)

Иначе

f(i, j, k) = max( f(i – 1, j, k), f(i, j – 1, k), f(i, j, k – 1) )

 

Реализация алгоритма

Входные три последовательности храним в массивах a, b, c. Для нахождения их НОП объявим массив dp.

 

#define MAX 110

int a[MAX], b[MAX], c[MAX];

int dp[MAX][MAX][MAX];

 

Читаем три входные последовательности.

 

scanf("%d", &n);

for (i = 1; i <= n; i++)

  scanf("%d", &a[i]);

scanf("%d", &m);

for (i = 1; i <= m; i++)

  scanf("%d", &b[i]);

scanf("%d", &k);

for (i = 1; i <= k; i++)

  scanf("%d", &c[i]);

 

Вычисляем НОП, заполняем массив dp.

 

for (u = 1; u <= n; u++)

for (v = 1; v <= m; v++)

for (w = 1; w <= k; w++)

{

  if ((a[u] == b[v]) && (a[u] == c[w]))

    dp[u][v][w] = dp[u - 1][v - 1][w - 1] + 1;

  else

   dp[u][v][w] = max(dp[u - 1][v][w], max(dp[u][v - 1][w], dp[u][v][w - 1]));

}

 

Выводим ответ.

 

printf("%d\n", dp[n][m][k]);