Динамическое программирование и DSU

Задача: кузнечик

Как бы вы решили эту задачу?

Первая попытка: рекурсия

Наблюдение: чтобы попасть в позицию n, нужно прийти из n-1, n-2 или n-3

База: f(0) = 1, f(1) = 1, f(2) = 2

int f(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n-1) + f(n-2) + f(n-3);
}
  

f(5) → f(4) + f(3) + f(2)
         ↓       ↓
       f(3)+f(2)+f(1)  f(2)+f(1)+f(0)
         ↓
       f(2)+f(1)+f(0) ...

Решение: запомнить результаты

int memo[100001];
bool computed[100001];

int f(int n) {
    if (n <= 0) return (n == 0) ? 1 : 0;
    if (computed[n]) return memo[n];
    computed[n] = true;
    memo[n] = f(n-1) + f(n-2) + f(n-3);
    return memo[n];
}
      

vector<long long> dp(n + 1);
dp[0] = 1; dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++)
    dp[i] = (dp[i-1] + dp[i-2]
           + dp[i-3]) % MOD;
cout << dp[n];
      

Сложность: O(n) — каждое значение считается ровно один раз

Рецепт DP: 4 шага

Задача: LIS (Longest Increasing Subsequence)

Полный перебор — 2ⁿ подмножеств. При n = 5000 нереально. Нужен DP!

Состояние и рекуррентность

Заполнение таблицы: пример

Массив: a = [3, 1, 4, 1, 5, 9, 2, 6]

LIS за O(n²): полный код

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);

    cout << *max_element(dp.begin(), dp.end()) << "\n";
    return 0;
}
  

Сложность: O(n²) — два вложенных цикла

Ускорение: O(n log n)

Идея: поддерживаем массив tail[], где tail[k] = наименьший последний элемент возрастающей подпоследовательности длины k+1

Свойство: массив tail[] всегда отсортирован!

LIS за O(n log n): код

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    vector<int> tail;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tail.begin(), tail.end(), a[i]);
        if (it == tail.end())
            tail.push_back(a[i]);
        else
            *it = a[i];
    }
    cout << tail.size() << "\n";
    return 0;
}
  

• lower_bound — находит первый элемент ≥ a[i]
• Если такого нет — a[i] больше всех, удлиняем LIS
• Сложность: O(n log n)

Задача: пути в сетке с препятствиями

.  .  .  .
.  *  .  .
.  .  .  .
.  .  *  .

DP на сетке: формулировка

dp[i-1][j]
     ↓
dp[i][j-1] → dp[i][j]

Заполнение таблицы

.  .  .  .
.  *  .  .
.  .  .  .
.  .  *  .

Код: CSES 1638

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

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<string> grid(n);
    for (auto& s : grid) cin >> s;

    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    dp[0][0] = (grid[0][0] == '.') ? 1 : 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '*') { dp[i][j] = 0; continue; }
            if (i > 0) dp[i][j] += dp[i-1][j];
            if (j > 0) dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    }
    cout << dp[n-1][n-1] << "\n";
    return 0;
}
  

Сложность: O(n²) по времени и памяти

Как выглядит DP на сетке

(1,1) → → → →
  ↓       ↓
  ↓   *   ↓
  ↓       ↓
  ↓ → → (n,n)

Общий паттерн: dp[i][j] зависит от соседей «выше» и «левее» по порядку заполнения.

Задача: подсчёт путей в графе

1 → 2 → 4
1 → 3 → 4
2 → 3

Наблюдение: это обобщение задачи на сетке! Сетка — частный случай DAG.

DP на DAG = топсорт + рекуррентность

Пример: подсчёт путей

Граф: 1 → 2, 1 → 3, 2 → 3, 2 → 4, 3 → 4

Топологический порядок: [1, 2, 3, 4]

Код: CSES 1681

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);

    vector<long long> dp(n + 1, 0);
    dp[1] = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            dp[v] = (dp[v] + dp[u]) % MOD;
            if (--indeg[v] == 0) q.push(v);
        }
    }
    cout << dp[n] << "\n";
    return 0;
}
  

Сложность: O(n + m)

Вариации DP на DAG

• Длиннейший путь в DAG: dp[v] = max(dp[u] + 1) по входящим рёбрам
• Кратчайший путь в DAG (с весами): dp[v] = min(dp[u] + w(u,v))
• Количество путей с максимальной длиной: комбинация двух массивов

Паттерны DP: сводка

DP рецепт — запомните навсегда

Обед! Возвращаемся в 14:00 к DSU.

Задача: динамическая связность

5 городов. Дороги добавляются: 1-2, 3-4, 1-3
Запрос: связаны 2 и 4? → ДА (2-1-3-4)
Запрос: связаны 2 и 5? → НЕТ

Как решать?

Наивный подход: BFS/DFS каждый раз

DSU: Disjoint Set Union

Другие названия: Union-Find, система непересекающихся множеств

Ключевое свойство: x и y в одном множестве ⇔ find(x) == find(y)

Представление: лес деревьев

      1
     / \
    2   3
    |
    5
Лидер: 1

    4
    |
    6

Лидер: 4

find(5): 5 → 2 → 1 (поднимаемся до корня)

find(6): 6 → 4

Базовая реализация

vector<int> parent;

void make(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++)
        parent[i] = i;  // каждый — сам себе лидер
}

int find(int x) {
    while (parent[x] != x)
        x = parent[x];
    return x;
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y)
        parent[x] = y;  // подвесить x под y
}

bool same(int x, int y) {
    return find(x) == find(y);
}
  

• make: O(n) — инициализация
• find: O(глубина дерева) — идём до корня
• unite: O(find) — находим лидеров и соединяем

Проблема: вырождение в цепочку

unite(1, 2): parent[1] = 2
unite(2, 3): parent[2] = 3
unite(3, 4): parent[3] = 4
unite(4, 5): parent[4] = 5

Результат: цепочка 1 → 2 → 3 → 4 → 5

1 → 2 → 3 → 4 → 5
find(1) = O(n)

      5
   / | \ \
  1  2  3  4
find(1) = O(1)

Как сделать деревья плоскими?

Path Compression (сжатие путей)

Идея: при вызове find(x) — перенаправить все пройденные вершины напрямую к корню

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}
  

1 → 2 → 3 → 4

    4
  / | \
 1  2  3

Все вершины на пути теперь ссылаются напрямую на корень. Следующие вызовы find — O(1)!

Union by Rank/Size

Идея: при объединении подвешивать меньшее дерево под большее

vector<int> sz;  // sz[x] = размер множества (только для корней)

void make(int n) {
    parent.resize(n);
    sz.assign(n, 1);
    for (int i = 0; i < n; i++)
        parent[i] = i;
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    parent[y] = x;     // подвешиваем меньшее (y) под большее (x)
    sz[x] += sz[y];
}
  

Гарантия: глубина дерева ≤ log₂(n)

DSU: финальный код

struct DSU {
    vector<int> parent, sz;

    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
    }

    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};
  

Сложность: O(α(n)) на операцию (α — обратная функция Аккермана, ≤ 4 для всех практических n)

Сжатие путей: визуализация

7 → 5 → 3 → 1 (корень)

После find(7):
      1
    / | \
   3  5  7

Union by Size: пример

     a
   / | \
  .  .  .
  |
  .

  b
  |
  .

Результат:
       a
     / | \ \
    .  .  .  b
    |        |
    .        .

Почему O(α(n)) — это «почти O(1)»

Итеративная версия find

Проблема: рекурсивный find может переполнить стек при очень длинных цепочках

int find(int x) {
    int root = x;
    while (parent[root] != root)
        root = parent[root];
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}
  

Два прохода: первый — находим корень, второй — перенаправляем все вершины

Задача: строительство дорог

n=5, дороги: (1,2), (3,5), (1,3)
После (1,2): 4 компоненты, макс = 2
После (3,5): 3 компоненты, макс = 2
После (1,3): 2 компоненты, макс = 4

Решение: DSU + отслеживание

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

struct DSU {
    vector<int> parent, sz;
    int components, max_size;

    DSU(int n) : parent(n), sz(n, 1), components(n), max_size(1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
        components--;
        max_size = max(max_size, sz[x]);
    }
};

int main() {
    int n, m; cin >> n >> m;
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--; v--;
        dsu.unite(u, v);
        cout << dsu.components << " " << dsu.max_size << "\n";
    }
}
  

Сложность: O(m · α(n)) ≈ O(m)

MST: алгоритм Крускала

Задача: найти минимальное остовное дерево (MST) — подмножество рёбер, соединяющее все вершины с минимальной суммой весов.

Сложность: O(m log m + m · α(n)) = O(m log m) (сортировка доминирует)

MST: код (CSES 1675)

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

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x; sz[x] += sz[y];
        return true;
    }
};

int main() {
    int n, m; cin >> n >> m;
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) { cin >> u >> v >> w; u--; v--; }
    sort(edges.begin(), edges.end());

    DSU dsu(n);
    long long total = 0;
    int count = 0;

    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) { total += w; count++; }
    }
    cout << (count == n - 1 ? to_string(total) : "IMPOSSIBLE") << "\n";
}
  

Замечание: unite возвращает bool — true если объединение произошло (ребро добавлено в MST)

Где ещё нужен DSU

1. Динамическая связность — проверка «в одной ли компоненте»
2. Алгоритм Крускала — MST за O(m log m)
3. Обработка запросов оффлайн — если запросы можно переупорядочить
4. Подсчёт компонент связности — добавление рёбер по одному
5. Задачи на объединение множеств — с отслеживанием размера, минимума, максимума

Практика: 15 минут

Поднимайте руку, если нужна помощь!

Итоги последнего дня

Спасибо за неделю! Удачи на IOI!