Разбор задачи «Хранители музейных маршрутов»

Идея задачи

Дан массив чисел. Нужно найти не длину наибольшей возрастающей подпоследовательности, а количество всех наибольших строго возрастающих подпоследовательностей.

Это важное отличие от классической задачи на LIS:

• в обычной версии нас интересует только максимальная длина;
• здесь нужно ещё и посчитать, сколько способов получить эту максимальную длину.

Подпоследовательность получается удалением некоторых элементов без изменения порядка оставшихся. Возрастание должно быть строгим, то есть каждый следующий элемент больше предыдущего.

Что мешает решить задачу слишком просто

Если бы нужно было найти только длину LIS, можно было бы вспомнить классическое решение за O(n log n). Но здесь этого уже недостаточно: нам нужно считать количество способов.

Для этой задачи естественно использовать динамическое программирование по позициям за O(n^2).

Динамика

Будем рассматривать каждую позицию i как конец некоторой возрастающей подпоследовательности.

Для каждой позиции сохраним два значения:

• len[i] — длина наибольшей строго возрастающей подпоследовательности, которая заканчивается в i;
• cnt[i] — количество таких подпоследовательностей длины len[i], которые заканчиваются в i.

Начальные значения

Любой элемент сам по себе образует возрастающую подпоследовательность длины 1.

Поэтому изначально:

• len[i] = 1
• cnt[i] = 1

для всех i.

Переход

Чтобы посчитать значения для позиции i, переберём все позиции j < i.

Если a[j] < a[i], то элемент a[i] можно поставить после подпоследовательности, заканчивающейся в j.

Тогда возможны два случая.

Случай 1. Нашли более длинную подпоследовательность

Если

len[j] + 1 > len[i],

то мы нашли лучший вариант закончить подпоследовательность в i.

Тогда:

• len[i] = len[j] + 1
• cnt[i] = cnt[j]

Почему количество просто присваивается? Потому что сейчас все лучшие подпоследовательности для i приходят именно из j.

Случай 2. Нашли ещё один способ получить ту же лучшую длину

Если

len[j] + 1 == len[i],

то найден ещё один источник подпоследовательностей той же максимальной длины.

Тогда:

• cnt[i] += cnt[j]

Как получить ответ

После того как мы посчитали len[i] и cnt[i] для всех позиций:

1. находим максимальную длину best = max(len[i]);
2. суммируем все cnt[i], для которых len[i] == best.

Именно это и будет количеством всех LIS в массиве.

Разберём пример

Пусть дан массив:

1 3 5 4 7

Посмотрим, что получится.

• 1 → длина 1, количество 1
• 3 можно поставить после 1 → длина 2, количество 1
• 5 можно поставить после 1, 3, лучший вариант через 3 → длина 3, количество 1
• 4 можно поставить после 1, 3, лучший вариант тоже длины 3, количество 1
• 7 можно поставить после 5 и после 4

В результате:

• через 5 получаем подпоследовательность длины 4
• через 4 тоже получаем подпоследовательность длины 4

Итого ответ равен 2.

Это подпоследовательности:

• 1, 3, 5, 7
• 1, 3, 4, 7

Почему решение корректно

Докажем идею кратко.

Рассмотрим произвольную позицию i. Любая строго возрастающая подпоследовательность, заканчивающаяся в i, перед этим должна оканчиваться в некоторой позиции j < i, где a[j] < a[i].

Значит, лучшая подпоследовательность для i получается продлением одной из лучших подпоследовательностей для подходящих j.

• Если найден более длинный вариант, мы обязаны его выбрать и забыть более короткие.
• Если найден другой вариант той же длины, его нужно добавить к числу способов.

Таким образом, len[i] действительно хранит максимальную длину возрастающей подпоследовательности, заканчивающейся в i, а cnt[i] — количество способов получить именно эту длину.

После этого сумма cnt[i] по всем позициям с глобально максимальной длиной даёт количество всех LIS во всём массиве.

Оценка сложности

Мы перебираем все пары j < i, поэтому:

• время: O(n^2)
• память: O(n)

Для ограничений порядка n <= 2000 такое решение отлично подходит.

Реализация на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> len(n, 1), cnt(n, 1);
    int best = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                } else if (len[j] + 1 == len[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        best = max(best, len[i]);
    }

    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (len[i] == best) {
            answer += cnt[i];
        }
    }

    cout << answer << '\n';
    return 0;
}

Реализация на Python

n = int(input())
a = list(map(int, input().split()))

length = [1] * n
count = [1] * n

best = 1

for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            if length[j] + 1 > length[i]:
                length[i] = length[j] + 1
                count[i] = count[j]
            elif length[j] + 1 == length[i]:
                count[i] += count[j]

    best = max(best, length[i])

answer = 0
for i in range(n):
    if length[i] == best:
        answer += count[i]

print(answer)

На что обратить внимание

1. Здесь считаются подпоследовательности по индексам

Если одинаковые значения стоят в разных местах массива, это всё равно разные способы выбрать подпоследовательность.

Например, для массива

2 2 2 2 2

длина LIS равна 1, а количество равно 5, потому что можно выбрать любой из пяти элементов.

2. Возрастание строгое

Нужно проверять именно

a[j] < a[i]

а не <=.

3. Нельзя складывать количества всегда

Если найден более длинный вариант, надо не прибавлять, а перезаписать:

• новая лучшая длина;
• новое количество способов.

Это одна из самых частых ошибок в такой задаче.

Типичные ошибки

Ошибка 1. Хранить только длину, но не количество

Так можно найти LIS, но нельзя узнать, сколько их.

Ошибка 2. При улучшении длины делать cnt[i] += cnt[j]

Нужно именно:

• cnt[i] = cnt[j], если нашли более длинный вариант;
• cnt[i] += cnt[j], если нашли ещё один вариант той же длины.

Ошибка 3. Использовать нестрогое сравнение

Если написать a[j] <= a[i], задача уже станет другой.

Ошибка 4. Суммировать не те позиции в конце

В ответ входят только те i, для которых len[i] равно глобальному максимуму.

Вывод

Эта задача — хорошее продолжение классической LIS.

Здесь важно научиться:

• хранить состояние не только про оптимальное значение, но и про число способов;
• аккуратно писать переходы в динамике;
• различать случаи «нашли лучший вариант» и «нашли ещё один лучший вариант».

Если идея обычной LIS уже понятна, то это очень естественный следующий шаг в изучении динамического программирования.