Динамика по префиксу и значению последнего элемента
Динамика по префиксу и значению последнего элемента
Пусть, дана последовательность $a_1,\ldots,a_n$, с максимальным значением $A$. Требуется найти длину наибольшей такой подпоследовательности, что ее элементы отличаются на более, чем на 1. Воспользуемся динамическим программированием, где $dp[j]$ будет обозначать ответ с последним взятым элементом, равным $j$. Будем обновлять и хранить актуалььным весь массив $dp$ целиком, проходясь по массиву $a$ слева направо.
Соответственно для каждого $i$ переходы можно делать только из таких $j$, что $|a[i]-j|\leq 1$.
1 for (int i = 1; i <= n; I++) {
2 dp[a[i]] += 1
3 if (a[i] > 0) {
4 dp[a[i]] = max(dp[a[i]], dp[a[i] - 1] + 1);
5 }
6 if (a[i] < A) {
7 dp[a[i]] = max(dp[a[i]], dp[a[i] + 1] + 1);
8 }
9 }
Это решение за $O(n + A)$.
Однако заметим, что если вместо массива использовать unordered_map, то асимптотика решения будет $O(n)$.
Заметим, что вот эти две идеи встречаются в задачах наиболее часто:
- хранить в $dp[i]$ ответ для $i$-ого префикса. Как в рюкзаке (где можно пользоваться $i$ первыми предметами), НВП(где ответ на префиксе длины $i$) и НОП (где ответ для префиксов длины $i$ и $j$).
- хранить в $dp[i]$ ответ для последовательностей, заканчивающихся на $i$.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin