Динамика по префиксу и значению последнего элемента

Динамика по префиксу и значению последнего элемента

Пусть, дана последовательность $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