- Используя бинпоиск \(O(n \log n)\) ¶
- Рюкзак¶
- Динамического программирования. \(O(NW)\) ¶
- Задача о наибольшей возрастающей подпоследовательности
- Псевдокод алгоритма
- Решение за O(N log N)
- Псевдокод алгоритма
- Ещё одно решение за О(N log N)
- См. также
- Примечания
- Наибольшая возрастающая последовательность на отрезке
Используя бинпоиск \(O(n \log n)\) ¶
Используя функцию \(upper_bound\) (который возвращает позицию первого элемента, строго большего данного):
#include using namespace std; #define ll long long #define INF (long long) 1e18 int main() ll n, t; cin >> n; vectorll> a(n); for (int i = 0; i n; i++) cin >> a[i]; > vectorll> d (n + 1, INF); d[0] = -INF; vectorll> p (n); vectorll> no (n + 1); no[0] = -1; for (ll i = 0; i n; i++) ll j = upper_bound(d.begin(), d.end(), a[i]) - d.begin() - 1; if (d[j] a[i] && a[i] d[j + 1]) d[j + 1] = a[i]; p[i] = no[j]; no[j + 1] = i; > > vectorint> result; for (int i = n; i >= 1; i--) if (d[i] != INF) for (int cur = no[i]; cur != -1; cur = p[cur]) result.push_back (cur); break; > reverse(result.begin(), result.end()); cout <result.size() <"\n"; for (unsigned i = 0; i result.size(); i++) cout <result[i] + 1 <" "; return 0; >
НОП — наибольшая общая подпоследовательность
Последовательность \(Z=⟨z_1,z_2,…,z_k⟩\) является подпоследовательностью (англ. subsequence) последовательности \(X=⟨x_1,x_2,…,x_m⟩\) , если существует строго возрастающая последовательность \(⟨i_1,i_2,…,i_k⟩\) индексов \(X\) таких, что для всех \(j=1,2,…,k\) выполняется соотношение \(x_=z_j\) .
Пусть имеются последовательности \(X=⟨x_1,x_2,…,x_m⟩\) и \(Y=⟨y_1,y_2,…,y_n⟩\) . Необходимо найти \(LCS(X,Y)\)
Рюкзак¶
Дано \(N\) предметов, \(W\) — вместимость рюкзака, \(w=\) — соответствующий ему набор положительных целых весов, \(p=\) — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин \(B=\) , где \(b_i=1\) , если предмет \(n_i\) включен в набор, \(b_i=0\) , если предмет \(n_i\) не включен, и такой что:
Динамического программирования. \(O(NW)\) ¶
Источник
Задача о наибольшей возрастающей подпоследовательности
Построим массив [math]d[/math] , где [math]d[i][/math] — это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом [math]i[/math] . Массив будем заполнять постепенно — сначала [math]d[0][/math] , потом [math]d[1][/math] и т.д. Ответом на нашу задачу будет максимум из всех элементов массива [math]d[/math] . Заполнение массива будет следующим: если [math]d[i] = 1[/math] , то искомая последовательность состоит только из числа [math]a[i][/math] . Если [math]d[i] \gt 1[/math] , то перед числом [math]a[i][/math] в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент [math]a[j](j = 0. i — 1)[/math] , но такой, что [math]a[j] \lt a[i][/math] . Пусть на каком-то шаге нам надо посчитать очередное [math]d[i][/math] . Все элементы массива [math]d[/math] до него уже посчитаны. Значит наше [math]d[i][/math] мы можем посчитать следующим образом: [math]d[i] = 1 + \max\limits_[/math] при условии, что [math]a[j] \lt a[i][/math] .
Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив [math]prev[0. n — 1][/math] , где [math]prev[i][/math] будет означать индекс в массиве [math]a[][/math] , при котором достигалось наибольшее значение [math]d[i][/math] . Для вывода ответа будем идти от элемента с максимальным значениям [math]d[i][/math] по его предкам.
Псевдокод алгоритма
vector findLIS(vector a): int n = a.size //размер исходной последовательности int prev[0..n - 1] int d[0..n - 1] for i = 0 to n - 1 d[i] = 1 prev[i] = -1 for j = 0 to i - 1 if (a[j] < a[i] and d[j] + 1 > d[i]) d[i] = d[j] + 1 prev[i] = j pos = 0 // индекс последнего элемента НВП length = d[0] // длина НВП for i = 0 to n - 1 if d[i] > length pos = i length = d[i] // восстановление ответа vector answer while pos != -1 answer.push_back(a[pos]) pos = prev[pos] reverse(answer) return answer
Решение за O(N log N)
Для более быстрого решения данной задачи построим следующую динамику: пусть [math]d[i](i = 0. n)[/math] — число, на которое оканчивается возрастающая последовательность длины [math]i[/math] , а если таких чисел несколько — то наименьшее из них. Изначально мы предполагаем, что [math]d[0] = -\infty[/math] , а все остальные элементы [math]d[i] =[/math] [math]\infty[/math] . Заметим два важных свойства этой динамики: [math]d[i — 1] \leqslant d[i][/math] , для всех [math]i = 1. n[/math] и каждый элемент [math]a[i][/math] обновляет максимум один элемент [math]d[j][/math] . Это означает, что при обработке очередного [math]a[i][/math] , мы можем за [math] O(\log n) [/math] c помощью двоичного поиска в массиве [math]d[/math] найти первое число, которое больше либо равно текущего [math]a[i][/math] и обновить его.
Для восстановления ответа будем поддерживать заполнение двух массивов: [math]pos[/math] и [math]prev[/math] . В [math]pos[i][/math] будем хранить индекс элемента, на который заканчивается оптимальная подпоследовательность длины [math]i[/math] , а в [math]prev[i][/math] — позицию предыдущего элемента для [math]a[i][/math] .
Псевдокод алгоритма
vector findLIS(vector a): int n = a.size //размер исходной последовательности int d[0..n] int pos[0..n] int prev[0..n - 1] length = 0 pos[0] = -1 d[0] = -INF for i = 1 to n d[i] = INF for i = 0 to n - 1 j = binary_search(d, a[i]) if (d[j - 1] < a[i] and a[i] < d[j]) d[j] = a[i] pos[j] = i prev[i] = pos[j - 1] length = max(length, j) // восстановление ответа vector answer p = pos[length] while p != -1 answer.push_back(a[p]) p = prev[p] reverse(answer) return answer
Ещё одно решение за О(N log N)
Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной [1] .
Само табло представляет из себя расположение [math]n_1+n_2+. +n_M[/math] различных целых чисел в массиве строк, выровненных по левому краю, где в [math]i[/math] строке содержится [math]n_i[/math] элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент [math]a_i[/math] , если он больше либо равен [math]n_j[/math] , где [math]j[/math] — длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент [math]b[/math] , который больше данного [math]a_i[/math] . Поставить элемент [math]a[/math] вместо [math]b[/math] . С элементом [math]b[/math] требуется провести те же действия, что и с [math]a[/math] , только уже на [math]i+1[/math] строке табла.
Пример построения табла на массиве [math]a = [ 3, 4, 9, 2, 5, 1 ][/math] :
1. Берём элемент [math]3[/math] . Видим, что [math]3 \gt 0[/math] , который расположен на первой строке в ячейке с индексом [math]j = 0[/math] . Увеличиваем [math]j[/math] и [math]t[i][j] = 3[/math] .
2. Берём элемент [math]4[/math] . Видим, что [math]4 \gt 3[/math] . Увеличиваем [math]j[/math] и [math]t[i][j] = 4[/math] .
3. Аналогично для элемента [math]9[/math] .
4. Берём элемент [math]2[/math] . Так как [math]2 \lt 9[/math] , то бинарным поиском находим нужную нам позицию [math]z[/math] , такую, что [math]t[i][z-1] \leqslant 2 \lt t[i][z][/math] . В данном случае это первая позиция. Присваиваем [math]t[i][z] = 2[/math] и проделываем такую же операцию, но для строки с индексом [math]i+1[/math] .
5. Аналогично для элемента [math]5[/math] .
6. Аналогично для элемента [math]1[/math] .
Таким образом, длина наибольшей возрастающей подпоследовательности для массива [math]a[/math] равна [math]3[/math] (например, подпоследовательность из элементов [math][ 3, 4, 9 ][/math] ).
См. также
Примечания
Источник
Наибольшая возрастающая последовательность на отрезке
В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз.
Поглядываю на дерево отрезков, но как не пытаюсь, никак не получается реализовать вообще.
Наибольшая возрастающая подпоследовательность
Дна последовательность, нужно найти её наибольшую возрастающую подпоследовательность. Входные.
Наибольшая возрастающая подпоследовательность за O(NlogN)
Здравствуйте! Вот тут написал код НВП за О(NlogN).Но на тестирующей системе он выдает на тесты.
Наибольшая возрастающая подпоследовательность (LIS)
Доброго времени суток! Я не сильно разбираюсь в шарпе(совсем) и при выполнении одного задания.
Сообщение от ThePonyCoder 
Сообщение от ThePonyCoder
В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз.
Пример:
Есть массив
Задаём границы отрезков.
L1 = 1. R1 = 3
Макс НВП здесь будет
L2 = 5. R2 = 7
НВП
L3 = 4. R2 = 7
НВП
Сообщение от Shamil1
Возрастающая последовательность
Задание: Написать программу, которая проверяет, представляют ли элементы введенного с клавиатуры.
Возрастающая последовательность
Дано n вещественных чисел, определите, образует ли она длину возрастающей последовательности
возрастающая последовательность
необходимо удалить из заданного массива 4 элемента так, чтобы оставшиеся образовали возрастающую.
Возрастающая последовательность
Ребят, помогите написать скрипт, нужно определить, образуют ли набранные в командной строке числа.
Источник