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

Question

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

Я пытаюсь понять алгоритм, который дает мне количество увеличивающихся подпоследовательностей длины K в массиве за время O (nКвойти (п)). Я знаю, как решить эту самую проблему, используя алгоритм O (k * n ^ 2). Я посмотрел и обнаружил, что это решение использует BIT (Fenwick Tree) и DP. Я также нашел некоторый код, но я не смог его понять.

Вот некоторые ссылки, которые я посетил, которые были полезны.

Здесь, в ТАК

Topcoder форум

Случайная веб-страница

Я был бы очень признателен, если бы кто-нибудь помог мне понять этот алгоритм.

5

algorithm c++fenwick-tree lis

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я воспроизводю свой алгоритм из Вот, где объясняется его логика:

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time)
have a certain length

for i = 1 to n do   dp[i, 1] = 1

for p = 2 to k do // for each length this time   num = {0}

for i = 2 to n do
// note: dp[1, p > 1] = 0

// how many that end with the previous element
// have length p - 1
num[ array[i - 1] ] += dp[i - 1, p - 1] *1*

// append the current element to all those smaller than it
// that end an increasing subsequence of length p - 1,
// creating an increasing subsequence of length p
for j = 1 to array[i] - 1 do *2*
dp[i, p] += num[j]

Вы можете оптимизировать *1* а также *2* используя деревья сегментов или деревья с двоичными индексами. Они будут использованы для эффективной обработки следующих операций на num массив:

Дано (x, v) добавлять v в num[x] (актуально для *1*);
Дано xнайти сумму num[1] + num[2] + ... + num[x] (актуально для *2*).

Это тривиальные проблемы для обеих структур данных.

Замечания: Это будет иметь сложность O(n*k*log S), где S верхняя граница значений в вашем массиве. Это может или не может быть достаточно хорошим. Сделать это O(n*k*log n)Вам нужно нормализовать значения вашего массива перед запуском вышеуказанного алгоритма. Нормализация означает преобразование всех значений массива в значения, меньшие или равные n, Итак, это:

5235 223 1000 40 40

становится:

4 2 3 1 1

Это можно сделать с помощью сортировки (сохраните исходные индексы).

6