5138. Возрастающая подпоследовательность

Задана последовательность целых чисел. Найдите количество её возрастающих подпоследовательностей.

Вход. Первая строка содержит длину последовательности n (1 ≤ n ≤ 500), а вторая – её элементы (натуральные числа, меньшие 5000).

Выход. Выведите количество возрастающих подпоследовательностей.

Пример входа 1	Пример выхода 1
3 1 2 3	7
Пример входа 2	Пример выхода 2
3 3 1 2	4

РЕШЕНИЕ

динамическое программирование

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

Пусть m₀, m₁, …, m_n-1 – входная последовательность. Пусть dp[i] хранит количество возрастающих подпоследовательностей для последовательности m₀, m₁, …, m_i. Тогда:

· dp[0] = 1;

· dp[i] равно сумме таких dp[j], что j < i и m_j < m_i. То есть элемент m_i продолжает все подпоследовательности, которые заканчиваются в m_j. К dp[i] следует еще прибавить 1, посчитав подпоследовательность из одного элемента m_i.

В задаче следует использовать длинную арифметику. Воспользуемся языками программирования Java или Python.

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

Читаем длину последовательности n.

Scanner con = new Scanner(System.in);

int n = con.nextInt();

BigInteger res = new BigInteger("0");

Входную последовательность храним в массиве m. Объявим массив dp.

int m[] = new int[n];

BigInteger dp[] = new BigInteger[n];

for(int i = 0; i < n; i++)

{

m[i] = con.nextInt();

Инициализируем dp[i] = 1. Учитываем первой подпоследовательность, состоящую из одного числа: m_i.

dp[i] = BigInteger.ONE;

Прибавляем к dp[i] все такие dp[j], что j < i и m_j < m_i.

for(int j = 0; j < i; j++)

if(m[j] < m[i]) dp[i] = dp[i].add(dp[j]);

res = res.add(dp[i]);

}

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

System.out.println(res);