Занятие 4. Параллель BS — Динамическое программирование 1

1. Что такое динамическое программирование 6:19

1.1. Идея на одной задаче и четыре обязательных пункта 6:36

6:36 Динамическое программирование (ДП) лекция вводит не определением, а на примере. Сначала задача, а метод вырастает из неё.

6:58 Переборное мышление подсказывает: «на каждой позиции два варианта». Но последовательностей $2^N$, и перебирать их по одной нельзя. ДП заменяет перебор вычислением: ответ собирается из ответов на меньшие задачи.

7:35 Любое решение динамикой нужно описать четырьмя пунктами. Именно их лектор просит проговаривать каждый раз, и в этом конспекте они выделены в каждой задаче:

1. Определение — что именно хранится в ячейке массива dp. Без точного определения остальное невозможно проверить.
2. База — значения для самых маленьких параметров, которые не выражаются через другие.
3. Формула пересчёта (переход) — как значение ячейки получается через уже известные ячейки.
4. Ответ — в какой ячейке (или как по нескольким ячейкам) лежит ответ на исходную задачу.

8:01 В записи звучит замечание, что порядок «база — переход» можно менять местами: часто сначала записывают формулу, смотрят, к каким ячейкам она обращается, и только затем понимают, какие из них нужно заполнить в базе.

1.2. Первая попытка: одного индекса не хватает 8:54

8:54 Естественное определение: $dp_i$ — количество подходящих последовательностей длины $i$. База: $dp_0 = 1$ (пустая последовательность одна), $dp_1 = 2$ (0 и 1). Теперь переход: хотим получить последовательность длины $i$ из последовательности длины $i-1$, дописав символ.

10:20 И тут обнаруживается проблема. Дописывать можно 0 всегда, а 1 — только если предыдущий символ 0. Но в $dp_{i-1}$ лежат вместе последовательности, заканчивающиеся и на 0, и на 1, и по одному числу мы их не различаем. Вывод лектора: значения $dp_i$ недостаточно, нужно хранить ещё последний символ.

1.3. Состояние $dp_{i,c}$, база, переход и ответ 10:41

1. Определение. 10:41 $dp_{i,c}$ — количество подходящих последовательностей длины $i$, у которых последний символ равен $c$ ($c \in \{0, 1\}$).

2. База. 11:13 Сначала лектор хотел оставить $dp_{0,\cdot}$, но тут же заметил: последовательностей длины ноль, заканчивающихся на ноль, не существует, поэтому такую базу давать нельзя. Базу задают для длины один: $dp_{1,0} = 1$ (строка 0), $dp_{1,1} = 1$ (строка 1).

3. Переход. 11:56 $$dp_{i,1} = dp_{i-1,0}, \qquad dp_{i,0} = dp_{i-1,0} + dp_{i-1,1}.$$ Почему так. Последовательность длины $i$, заканчивающаяся на единицу, получается из последовательности длины $i-1$ дописыванием 1; предыдущий символ обязан быть нулём, потому что две единицы подряд запрещены, поэтому берём только $dp_{i-1,0}$. А если дописываем 0, то никаких ограничений нет, и подходят обе группы: и заканчивающиеся на ноль, и на единицу.

4. Ответ. 14:22 $dp_{N,0} + dp_{N,1}$ — количество последовательностей длины $N$, оканчивающихся на ноль, плюс оканчивающихся на единицу.

14:56 Лектор отмечает, что получилось что-то очень похожее на числа Фибоначчи. Это не совпадение: $dp_{i,1} = dp_{i-1,0}$, поэтому $dp_{i,0} = dp_{i-1,0} + dp_{i-2,0}$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // dp[i][c] — число строк длины i без «11», оканчивающихся на c
    vector<array<long long, 2>> dp(n + 1);
    dp[1] = {1, 1};                      // база: «0» и «1»
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];   // дописываем 0 к чему угодно
        dp[i][1] = dp[i - 1][0];                  // дописываем 1 только после 0
    }
    cout << dp[n][0] + dp[n][1] << "\n";      // ответ
}

1.4. Вопросы из чата 15:13

2. Наибольшая возрастающая подпоследовательность (НВП) 21:46

2.1. Условие и примеры 21:50

21:50 Дан массив из $n$ чисел. Нужно найти длину самой длинной строго возрастающей подпоследовательности: набора элементов массива (в исходном порядке, возможно, с пропусками), значения которых строго возрастают.

22:17 Пример лектора: у массива, содержащего числа 3, 6, 9, 10 в таком порядке, подпоследовательность 3 6 9 10 возрастающая, как и 3 6 8; а 3 7 6 не подходит, потому что семёрка больше шестёрки. Элементы можно пропускать: из 3 7 6 10 можно взять 3 7 10.

23:35 Начинаем с решения за квадрат.

2.2. Решение за $O(n^2)$ 23:35

1. Определение. 23:35 $dp_i$ — длина наибольшей возрастающей подпоследовательности, которая заканчивается ровно в элементе $a_i$.

   24:31 Один из участников предложил определение «заканчивается в $i$ или ранее» (то есть максимум по префиксу). Лектор возражает: тогда мы не будем знать, каким числом заканчивается подпоследовательность, а значит, не сможем понять, какие числа к ней можно дописать. Поэтому «ровно в $i$».

2. База. 25:39 В одноиндексной нумерации $dp_1 = 1$: одиночный элемент — возрастающая подпоследовательность длины один. Лектор работает в одноиндексной нумерации: нулевого элемента в массиве нет, поэтому «ответ для $i = 0$» равен нулю. (В нуль-индексации то же самое записывается как $dp_0 = 1$.)

3. Переход. 26:31 Первая идея участника — сравнить $a_i$ только с предыдущим $a_{i-1}$ и при $a_i > a_{i-1}$ взять $dp_{i-1} + 1$. Но это неверно: 27:21 если $a_i \le a_{i-1}$, то нельзя «обнулить» (ответ $1$): элемент мог бы продолжить более раннюю подпоследовательность. Пример из лекции: восьмёрка меньше стоящей перед ней десятки, но может продолжать подпоследовательность, заканчивающуюся на шестёрке. Правильная формула (27:56): перебираем все предыдущие $j < i$ и берём из подходящих максимум. $$dp_i = 1 + \max_{\substack{j < i \\ a_j < a_i}} dp_j,$$ а если подходящих $j$ нет, то $dp_i = 1$.

4. Ответ. 29:12 $\max_i dp_i$ — максимум по всем $i$: заранее неизвестно, где заканчивается самая длинная подпоследовательность.

29:51 Асимптотика. Для каждого $i$ просматриваем все $j < i$, итого $O(n^2)$ по времени и $O(n)$ по памяти.

// dp[i] — длина НВП, заканчивающейся ровно в a[i]
int lis_n2(const vector<int>& a) {
    int n = a.size(), ans = 0;
    vector<int> dp(n, 1);                 // база: сам элемент — подпоследовательность длины 1
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])               // a[i] можно дописать после a[j]
                dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);             // ответ — максимум по всем i
    }
    return ans;
}

2.3. Решение за $O(n \log n)$ 30:37

30:40 Один из участников предложил другое решение: идти по массиву и вести вспомогательный массив, куда числа записываются в нужную позицию бинарным поиском. Лектор оформила его как ДП с нестандартным состоянием.

1. Определение. 31:48 $d_\ell$ — наименьшее число, на которое может заканчиваться возрастающая подпоследовательность длины $\ell$, среди рассмотренных к этому моменту элементов. Размер массива $n+1$: длина может быть от $0$ до $n$.

2. База. 32:30 $d_0 = -\infty$, остальные $d_\ell = +\infty$. Смысл: подпоследовательность длины $0$ «заканчивается на минус бесконечность» — её можно продолжить любым числом. А $+\infty$ означает, что подпоследовательности такой длины пока не существует.

33:39 Дальше обрабатываем элементы по очереди и смотрим, какие подпоследовательности каждый может продолжить. Рассмотрим массив 3 7 6 10 8 9 (восстановлен по ходу объяснения):

• 34:36 3 может продолжить только подпоследовательность длины $0$. Теперь длина $1$ может заканчиваться на тройку: $d_1 = 3$.
• 35:10 7 продолжает длину $0$ и длину $1$. Длину $2$ получили впервые: $d_2 = 7$. Продолжить длину $2$ семёрка не может — там ещё бесконечность.
• 35:58 6 тоже продолжает длины $0$ и $1$, но не длину $2$ (после семёрки шестёрка идти не может). Выходит второй кандидат на длину $2$: теперь есть подпоследовательность, заканчивающаяся на $6$, а была на $7$. 36:21 Какая выгоднее? Та, что на шестёрке: у неё больше шансов, что следующее число окажется больше конца. Заменяем: $d_2 = 6$.
• 36:38 10 продолжает длину $2$: $d_3 = 10$. 8 продолжает длину $2$ (шестёрку), поэтому $d_3$ улучшается до $8$. 9 продолжает длину $3$: $d_4 = 9$.

37:12 Итог: $d = (-\infty,\,3,\,6,\,8,\,9)$. Возрастающая подпоследовательность длины $1$ может заканчиваться на $3$, длины $2$ — на $6$, длины $3$ — на $8$, длины $4$ — на $9$.

Ответ. 37:38 Количество значений в $d_1, d_2, \dots$, не равных $+\infty$ (то есть наибольшая длина $\ell$ с $d_\ell < +\infty$).

2.4. Как найти позицию и почему массив отсортирован 37:48

37:48 Формально: для очередного числа $x = a_i$ нужно найти позицию в $d$, куда его поставить. Участник говорит: lower_bound. Лектор спрашивает: почему можно применять бинарный поиск, то есть почему $d$ отсортирован?

38:15 Ответ из лекции. В начале $d$ возрастает: $-\infty,\ +\infty,\dots$. Пусть число $x$ встало в позицию $p$: слева от неё все значения меньше $x$ (это длины, которые $x$ может продолжить), а справа значения больше или равны $x$. Заменив $d_p$ (которое было $\ge x$) на $x$, мы сохраняем возрастание: слева значения меньше, справа не меньше. Так массив остаётся отсортированным. 39:27 В результате $x$ продолжает любую подпоследовательность из левой части, а правую продолжить не может; и выгодно заменить именно первое значение, не меньшее $x$, чтобы подпоследовательность той же длины оканчивалась на меньшее число.

40:05 Если число меньше всех. Например, встретилась двойка, а в $d_1$ лежит тройка. Двойка может продолжить только подпоследовательность длины $0$, то есть становится подпоследовательностью длины один, и тройку выгодно заменить на двойку.

// d[len] — наименьшее число, на котором может заканчиваться НВП длины len
int lis_nlogn(const vector<int>& a) {
    const int INF = INT_MAX, NINF = INT_MIN;
    int n = a.size();
    vector<int> d(n + 1, INF);
    d[0] = NINF;                                     // база
    for (int x : a) {
        // первая позиция, где d[len] >= x  (строгая НВП: равные тоже заменяем)
        int len = lower_bound(d.begin(), d.end(), x) - d.begin();
        d[len] = x;                                  // меняется ровно одна ячейка
    }
    int ans = 0;
    while (ans + 1 <= n && d[ans + 1] != INF) ans++;   // сколько ячеек заполнено
    return ans;
}

46:04 Асимптотика. Для каждого из $n$ чисел делаем один бинарный поиск за $O(\log n)$: итого $O(n \log n)$ по времени и $O(n)$ по памяти.

2.5. Как прийти к решению за $O(n \log n)$: вывод из двумерной динамики 50:56

50:56 В записи этот вывод рассказывают второй преподаватель в середине лекции (50:56, коротко) и ещё раз подробно после перерыва (2:21:36, с доказательствами). Ниже — объединённый рассказ. Идея: решение с массивом $d$ — это двумерная динамика, у которой лишний параметр убрали.

52:00 Шаг 1. Типовая попытка и где она ломается. Для массива чаще всего пробуют динамику «по префиксу»: $dp_i$ — ответ на первых $i$ элементах. Но зная ответ на префиксе длины $i$, ответ для $i+1$ посчитать нельзя: мы не знаем, на каком значении заканчивается самая длинная подпоследовательность, а значит, не знаем, можно ли её продолжить числом $a_{i+1}$. В решении за $n^2$ эту проблему обходили определением «заканчивается ровно в $i$». 53:02 Правило: если состояния не хватает, в него добавляют ещё один параметр.

55:38 Шаг 2. Кладём ответ в состояние. Добавим параметр $\ell$ — желаемую длину подпоследовательности — и в ячейке будем хранить то, что нужно для продолжения: наименьший возможный последний элемент. $$dp_{i,\ell} = \text{наименьший конец возрастающей подпоследовательности длины } \ell \text{ на первых } i \text{ элементах.}$$ Почему наименьший: чтобы подпоследовательность можно было продолжить числом $x$, важно только соотношение её последнего элемента с $x$; из подпоследовательностей одной длины лучшая — та, у которой конец меньше, так как ей подходит больше чисел. Ответ — наибольшее $\ell$, для которого $dp_{n,\ell} < +\infty$. 2:28:18 База: $dp_{0,0} = -\infty$, $dp_{0,\ell} = +\infty$ при $\ell > 0$.

54:15 Шаг 3. Слои почти одинаковы. Если выписать массивы $dp_{i,\cdot}$ по слоям $i = 0, 1, 2,\dots$, видно, что соседние слои различаются не больше чем в одной ячейке. Тогда не нужно хранить все слои: достаточно одного массива, в котором на каждом шаге меняется одна ячейка. Так получается массив $d$ из прошлого раздела. Остаётся доказать, что слои действительно отличаются в одной ячейке, и понять, в какой.

2.6. Доказательство: что меняется при добавлении $a_{i+1}$ 2:37:43

2:30:02 Переход от слоя $i$ к слою $i+1$ — добавление одного числа $a = a_{i+1}$. Либо мы его не используем (слой просто копируется), либо дописываем в конец какой-то подпоследовательности.

2:37:43 Лемма (возрастание слоя). Значения $dp_{i,0}, dp_{i,1}, \dots$ строго возрастают.

Доказательство (2:38:12, от противного). Пусть $\ell_1 < \ell_2$ и $x_1 = dp_{i,\ell_1} \ge x_2 = dp_{i,\ell_2}$. Возьмём подпоследовательность длины $\ell_2$, заканчивающуюся на $x_2$. Её $\ell_1$-й по счёту элемент $y$ строго меньше $x_2$ (подпоследовательность строго возрастает, а $\ell_1 < \ell_2$), то есть $y < x_2 \le x_1$. Начало этой подпоследовательности до $y$ — возрастающая подпоследовательность длины $\ell_1$ с концом $y < x_1$. Но $x_1$ по определению наименьший возможный конец длины $\ell_1$ — противоречие. Значит, $x_1 < x_2$ для любых $\ell_1 < \ell_2$. $\square$

2:43:34 Что делает число $a$. Из строгого возрастания слоя следует: найдётся позиция $p$ — первая, где $dp_{i,p} \ge a$. Разобьём слой на две части: слева значения меньше $a$, справа не меньше.

• Левая часть ($\ell < p$): не меняется. 2:33:30 Здесь $dp_{i,\ell} < a$: у длины $\ell$ уже есть конец меньше $a$, а дописывание $a$ даёт конец $a$, то есть хуже. Помочь им нечем.

• Позиция $p$: может измениться. 2:44:00 Чтобы улучшить длину $p$, надо к подпоследовательности длины $p-1$ с концом меньше $a$ приписать $a$. Такая подпоследовательность есть: $dp_{i,p-1} < a$ (левая часть); причём $p \ge 1$, потому что $dp_{i,0} = -\infty$ меньше любого числа. Получаем подпоследовательность длины $p$ с концом $a$. Если $dp_{i,p} = a$, ничего не меняется; если $dp_{i,p} > a$, оно заменяется на $a$.

• Правая часть ($\ell > p$): не меняется. 2:46:08 Чтобы улучшить длину $\ell$, надо приписать $a$ к подпоследовательности длины $\ell - 1 \ge p$, у которой конец меньше $a$. Но все концы длины $\ge p$ не меньше $a$ ($dp_{i,\ell-1} \ge dp_{i,p} \ge a$). Так что приписать $a$ нельзя.

2:47:11 Вывод. Переход от слоя $i$ к слою $i+1$ меняет не более одной ячейки — первую, где $dp \ge a$ (находится бинарным поиском, это lower_bound), на значение $a$. Поэтому вместо таблицы $n \times n$ хранится один массив $d$, а каждое добавление числа стоит $O(\log n)$.

2.7. Восстановление самой подпоследовательности 2:55:03

2:55:03 Массив $d$ хранит лишь концы, но саму подпоследовательность восстановить можно. В каждый момент при добавлении $a_i$ мы выбираем позицию $p$ — запомним её в массиве $pr_i = p$. Это длина самой длинной подпоследовательности, оканчивающейся ровно в $a_i$ (то же, что $dp_i$ в решении за $n^2$).

• 2:57:38 Найдём максимальное значение $L = \max_i pr_i$ — длина ответа. Выберем любую позицию $i$ с $pr_i = L$. 2:58:16 Если таких позиций несколько, для вывода какой-нибудь НВП подойдёт любая. Для лексикографически минимальной лектор советует брать самую правую из них (это замечание в конспекте не проверялось).
• 3:03:43 Идём справа налево и ищем первый элемент с $pr = L - 1$ — это предпоследний элемент ответа; затем ближайший левее элемент с $pr = L - 2$ и так далее. Найденные числа выписываем с конца и в конце переворачиваем.

// НВП с восстановлением ответа за O(n log n)
vector<int> lis_restore(const vector<int>& a) {
    const int INF = INT_MAX, NINF = INT_MIN;
    int n = a.size();
    vector<int> d(n + 1, INF), pr(n);
    d[0] = NINF;
    for (int i = 0; i < n; i++) {
        int len = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
        d[len] = a[i];
        pr[i] = len;                   // длина НВП, оканчивающейся в a[i]
    }
    int L = *max_element(pr.begin(), pr.end());
    vector<int> res;
    int need = L;
    for (int i = n - 1; i >= 0 && need > 0; i--)
        if (pr[i] == need) {           // ближайший слева элемент нужной длины
            res.push_back(a[i]);
            need--;
        }
    reverse(res.begin(), res.end());
    return res;
}

3. Наибольшая общая подпоследовательность (НОП) 58:51

3.1. Условие 58:51

58:51 Даны две строки $A$ и $B$. Нужно найти длину самой длинной строки, которая является подпоследовательностью (символы в исходном порядке, возможно, с пропусками) и $A$, и $B$.

59:30 Лектор поясняет на двух строках из букв A и B: общая подпоследовательность получается, если взять символы в том же порядке из обеих строк, пропуская лишние. Порядок нарушать нельзя, пропускать символы можно. Дальше строится динамика.

3.2. Определение, база, переход, ответ 1:01:13

1. Определение. 1:00:44 Первое предложение участника — хранить длину подпоследовательности, которая «в первой строке заканчивается в позиции $i$, а во второй в $j$» — лектор не принимает. 1:01:13 Принято определение: $dp_{i,j}$ — длина наибольшей общей подпоследовательности префикса $A$ длины $i$ и префикса $B$ длины $j$ (нумерация с единицы, чтобы удобнее было обращаться к $i-1$).

2. База. 1:02:36 $dp_{i,0} = dp_{0,j} = 0$: у пустого префикса с любой строкой нет общих символов.

3. Переход. 1:03:30 Смотрим на последние символы префиксов $A_i$ и $B_j$.

   • Если $A_i = B_j$, этот символ можно поставить в конец общей подпоследовательности: к лучшему ответу на префиксах без этих символов добавляется единица. $$dp_{i,j} = dp_{i-1,j-1} + 1.$$
   • Если $A_i \ne B_j$, то хотя бы один из них в общей подпоследовательности не участвует, и мы выбрасываем один из двух последних символов, оставляя другой префикс целиком: $$dp_{i,j} = \max(dp_{i-1,j},\ dp_{i,j-1}).$$

4. Ответ. 1:12:55 $dp_{n,m}$, где $n = |A|$, $m = |B|$.

// dp[i][j] — НОП префиксов a[0..i) и b[0..j)
int lcs_len(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));   // база: нули
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    return dp[n][m];
}

1:13:21 Асимптотика. Состояний $n \cdot m$, переход за $O(1)$: время и память $O(nm)$. На вопрос, можно ли быстрее (за $O(n + m)$ или $O((n+m)\log)$), лектор отвечает отрицательно.

3.3. Почему при равных символах не нужен максимум из трёх 1:08:29

1:08:29 Участник спрашивает: при $A_i = B_j$ можно ли написать $\max$ из трёх значений — $dp_{i-1,j}$, $dp_{i,j-1}$ и $dp_{i-1,j-1}+1$? Можно, но не нужно. Лекторская версия объяснения (1:11:26): если бы выгоднее было взять $dp_{i-1,j}$, то в ответе для префикса $A_{1..i-1}$ и $B_{1..j}$ последний символ $B_j$ уже совпал с каким-то более ранним символом $A$; но его можно сопоставить с $A_i$, ничего не потеряв. При неравных символах так сделать нельзя, и приходится искать равенство глубже в префиксах.

3.4. Восстановление ответа 1:14:04

1:14:04 Пусть нужно вывести не только длину, но и саму НОП. Лекция называет два подхода (1:17:03): обратный ход по таблице и массив родителей.

3.5. Обратный ход по таблице $dp$ 1:17:50

1:17:50 Таблица уже содержит всю информацию о том, откуда мы пришли в клетку. Идём из $(n, m)$ к $(0,0)$:

• 1:19:38 если $A_i = B_j$, символ входит в ответ: записываем его и переходим в $(i-1, j-1)$;
• 1:20:06 иначе по формуле выбирался максимум: сравниваем $dp_{i-1,j}$ и $dp_{i,j-1}$ и переходим туда, где значение больше (в записи лектор описывает это как «в сторону большего»); в ответ ничего не добавляется;
• идём, пока $i>0$ и $j>0$. Символы набираются с конца, поэтому в конце результат разворачивается (1:21:54).

1:22:18 Лектор показывает на маленьком примере, как идёт обратный ход; в этом конспекте полный пример с таблицей и выделенным путём — на рисунке выше (собственный пример: строки ABCBD и BDCAB, ответ BCB).

3.6. Массив родителей 1:25:39

1:25:39 Второй способ: прямо в каждой клетке хранить пару индексов — откуда мы в неё пришли (1:26:19). Тогда обратный ход не нужно «угадывать» сравнением значений: достаточно идти по родителям и добавлять в ответ символ тогда, когда переход был по диагонали при равных символах. Платим дополнительной памятью.

// НОП с восстановлением: обратный ход по таблице dp
string lcs_restore(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1
                                            : max(dp[i - 1][j], dp[i][j - 1]);
    string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {            // этот символ входит в ответ
            res += a[i - 1];
            i--; j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) i--;   // идём туда, где больше
        else j--;
    }
    reverse(res.begin(), res.end());           // набирали с конца
    return res;
}

4. Семинар: приёмы и задачи на ДП 3:06:53

2:49:24 После перерыва начинается семинар: второй преподаватель разбирает задачи из контеста вместе с участниками. Условия звучат устно, поэтому ниже они записаны так, как были заданы на семинаре; где формулировка осталась неполной, это оговорено.

4.1. Приём: массивы смещений dx, dy 3:06:53

3:06:53 Первый приём, который пригодится в задачах на сетке и лабиринтах. Когда из клетки можно сдвинуться в несколько сторон (север, юг, запад, восток и ещё четыре диагонали), вместо восьми однотипных if заводят два массива смещений длины $8$ и перебирают переходы циклом. 3:11:40 Асимптотика не меняется (восемь проверок остаются восемью проверками), зато код короче, и в нём меньше мест для опечаток.

// 8 направлений: С, СВ, В, ЮВ, Ю, ЮЗ, З, СЗ
const int dx[8] = {-1, -1, 0, 1, 1,  1,  0, -1};   // изменение номера строки
const int dy[8] = { 0,  1, 1, 1, 0, -1, -1, -1};   // изменение номера столбца

for (int k = 0; k < 8; k++) {
    int ni = i + dx[k], nj = j + dy[k];
    if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;   // вышли за поле
    if (grid[ni][nj] == '#') continue;                       // стена
    // ... переход из (i, j) в (ni, nj)
}

4.2. Задача «Поставки еды и две шахты» 3:12:31

3:15:38 Условие приходится повторить: шахты две; каждой шахте поставки даются в порядке прихода; сколько поставок получит каждая — неважно, важна только суммарная прибыль в тоннах. Отдельный ответ с самим распределением не требуется — достаточно числа.

1. Определение. 3:16:56 Хочется $dp_i$ — максимум угля на первых $i$ поставках. Но этого мало: прибавку от следующей поставки определяют две последние поставки каждой шахты, а в $dp_i$ их нет. Поэтому в состояние добавляют «хеш» — число, кодирующее эти четыре вида. 3:19:41 Хранить нужно по две последние поставки (а не три), потому что новая поставка в сумме с двумя предыдущими и образует три. Итого $dp_{i,h}$ — максимум угля, когда обработаны первые $i$ поставок, а состояние шахт описывает число $h$.

2. Размер состояния. 3:20:15 Каждая из четырёх позиций (две в первой шахте, две во второй) принимает одно из трёх значений, поэтому лектор получает $3^4 = 81$ состояние и асимптотику $O(81 \cdot N)$. 3:21:06 Лектор договаривается обозначать такие константы просто $K$: «$O(Kn)$», где $K$ — размер набора состояний.

3. База. 3:22:24 Для удобства добавляют нулевую поставку; $dp_{0,h} = 0$ при пустых шахтах.

4. Переход. 3:26:17 Проще считать «вперёд». Если известно $dp_{i,h}$, то поставку $a_{i+1}$ можно отдать первой шахте или второй, и состояние $h$ меняется на $h'$ (в соответствующей шахте старый «предпоследний» вид забывается, последний сдвигается, на его место встаёт новый). Прибавка угля равна числу различных видов среди новой поставки и двух предыдущих в этой шахте, и $dp_{i+1,h'}$ берётся как максимум по всем таким переходам. 3:28:21 Двух переходов именно два (какой шахте отдать), хеши у них получаются разные.

5. Ответ. Максимум по всем $h$ из $dp_{N,h}$.

// Виды 0..2, «пусто» = 3. Состояние шахты — две последние поставки (p, q), q — самая свежая.
// Состояние обеих шахт: h = ((p1*4 + q1)*4 + p2)*4 + q2  (0..255)
int gain(int p, int q, int x) {                // сколько тонн даст поставка x
    int mask = 1 << x;                         // множество различных видов
    if (q != 3) mask |= 1 << q;
    if (p != 3) mask |= 1 << p;
    return __builtin_popcount(mask);
}

int solve(const vector<int>& a) {
    vector<int> dp(256, -1), nd(256);
    dp[((3 * 4 + 3) * 4 + 3) * 4 + 3] = 0;     // обе шахты пусты
    for (int x : a) {
        fill(nd.begin(), nd.end(), -1);
        for (int h = 0; h < 256; h++) if (dp[h] >= 0) {
            int q2 = h % 4, p2 = h / 4 % 4, q1 = h / 16 % 4, p1 = h / 64;
            // поставка x уходит в первую шахту
            int h1 = ((q1 * 4 + x) * 4 + p2) * 4 + q2;
            nd[h1] = max(nd[h1], dp[h] + gain(p1, q1, x));
            // поставка x уходит во вторую шахту
            int h2 = ((p1 * 4 + q1) * 4 + q2) * 4 + x;
            nd[h2] = max(nd[h2], dp[h] + gain(p2, q2, x));
        }
        dp = nd;
    }
    return *max_element(dp.begin(), dp.end());
}

4.3. Задача: сколько неубывающих массивов с заданной суммой 3:31:40

3:34:45 Ход обсуждения. Сначала лектор пробует состояние «длина $i$ и последний элемент $x$»; сразу выясняется (3:37:25), что нужен ещё один параметр — сумма. Вводится $S$ — остаток суммы. Получается состояние из трёх параметров $dp_{i,x,S}$, а переход перебирает предыдущий последний элемент $x_1$ от $K$ до $x$ — слишком много (3:43:57 лектор называет такое решение «самым тупым» и ищет, как его ускорить). Дальше (3:46:00) замечено, что порядок циклов можно менять: фиксируем остаток $S$ и переходим от $x$ к $x+1$, и при этом в сумму по $x_1$ добавляется всего один новый член. Идея — получить префиксные суммы по $x_1$. 3:49:29 Но параметры $i$, $x$ и $S$ меняются одновременно, и сделать префиксные суммы напрямую не получается; обсуждение переходит к замене смысла параметра $S$ (3:51:33), но до готового решения не доходит, и семинар переходит к следующей задаче.

const long long MOD = 1e9 + 7;

long long count_arrays(int n, int k) {
    if (k > n) return 0;
    int r = n - k;                          // сумму r нужно набрать числами >= k
    vector<long long> ways(r + 1, 0);
    ways[0] = 1;                            // пустой набор (массив из одного элемента k)
    for (int x = k; x <= r; x++)            // номинал x
        for (int s = x; s <= r; s++)
            ways[s] = (ways[s] + ways[s - x]) % MOD;
    return ways[r];
}

4.4. Задача «Пловцы и дорожки» 3:56:26

3:57:49 Примеры лектора. Для массива $(3, 0, 1)$ подходит $(2, 1, 1)$: один человек перешёл на соседнюю дорожку, штраф $1$. Для $(8, 0, 2)$ подходит $(4, 3, 3)$; 4:00:12 штраф получается $5$, а не $4$, потому что одного из людей потревожили дважды — через него прошли сразу две границы.

Как считается штраф: сдвиги границ.

Как ограничить размер состояния.

4:03:15 Сколько людей может быть на одной дорожке. Допустим, на самой загруженной дорожке стоит $m$ человек. Соседние дорожки отличаются не более чем на единицу, поэтому на дорожках слева или справа от неё в лучшем случае $m-1, m-2, \dots$ человек (дальше, возможно, нули). Значит, сумма $S$ не меньше $m + (m-1) + \dots + 1 \approx m^2 / 2$, откуда $m \lesssim \sqrt{2S}$. 4:05:06 Если дорожек мало, то оценка другая: порядка $S/N + N/2$ (лектор называет её для случая «мало дорожек», а общую оценку — «корнем из $S$ плюс единица»). 4:08:08 Вывод лектора: не нужно перебирать все $S$ значений для последней дорожки, достаточно порядка $\sqrt S$.

Состояние и переход.

4:13:37 Состояние: $dp_{i,s,l}$ — минимальный штраф, если расставлены первые $i$ дорожек, в них суммарно $s$ человек, а на последней стоит $l$ человек. 4:14:07 Переход: на следующей дорожке будет $l-1$, $l$ или $l+1$ человек — три варианта, отсюда новая сумма $s + l'$. 4:15:48 Параметр «сумма» нужен, чтобы знать, где сейчас проходит граница после первых $i$ дорожек, и посчитать, на сколько людей её пришлось сдвинуть относительно исходной.

4:17:48 Лектор считает штраф перехода через префиксные суммы исходного массива и бинарный поиск позиции границы (4:18:05), затем (4:22:12) называет наивный вариант с подсчётом «руками» стоимостью $O(N)$ на переход и предлагает заранее подсчитать штрафы сдвигов в таблице (4:24:35). Асимптотика после этого — порядка $O(N \cdot S \cdot \sqrt S)$ (4:26:49); лектор отмечает, что фактически состояний меньше из-за ограничения на число людей. 4:27:29 Подставляя оценки, получаем порядка $10^8$ операций, которые по оценке лектора укладываются в ограничение по времени.

int min_penalty(const vector<int>& a) {
    const int INF = 1e9;
    int n = a.size(), S = accumulate(a.begin(), a.end(), 0);
    vector<int> P(n + 1, 0);                     // префиксные суммы исходных дорожек
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + a[i];
    int cap = 0;                                 // верхняя граница людей на дорожке
    for (;; cap++) {
        long long sum = 0;
        for (int j = 0; j < n; j++) sum += max(cap + 1 - j, 0);
        if (sum > S) break;
    }
    // dp[s][l]: расставлены первые i дорожек, в них s человек, на последней l
    vector<vector<int>> dp(S + 1, vector<int>(cap + 1, INF)), nd;
    for (int l = 0; l <= min(cap, S); l++) dp[l][l] = abs(P[1] - l);
    for (int i = 2; i <= n; i++) {
        nd.assign(S + 1, vector<int>(cap + 1, INF));
        for (int s = 0; s <= S; s++)
            for (int l = 0; l <= cap; l++) {
                if (dp[s][l] >= INF) continue;
                for (int nl = max(l - 1, 0); nl <= min(l + 1, cap); nl++) {
                    int ns = s + nl;
                    if (ns > S) continue;
                    nd[ns][nl] = min(nd[ns][nl], dp[s][l] + abs(P[i] - ns));
                }
            }
        dp.swap(nd);
    }
    int best = INF;
    for (int l = 0; l <= cap; l++) best = min(best, dp[S][l]);
    return best;
}

5. Итог занятия 4:28:13

Общее наблюдение по задачам: во всех трёх случаях исходная идея — «ответ на префиксе» — упиралась в нехватку информации в состоянии, и решение появлялось после добавления нужных параметров (последние поставки, остаток суммы, последняя дорожка и сумма). Именно так устроены и задачи лекции: НВП и строки без «11».

Сводка задач занятия.