Пересчет динамики по слоям - Алгоритмика
Пересчет динамики по слоям

Пересчет динамики по слоям

авторы Сергей Слотин Константин Амеличев
опубликовано 2019
обновлено авг. 29, 2021

Задача. Даны $n$ точек на прямой, отсортированные по своей координате $x_i$. Нужно найти $m$ отрезков, покрывающих все точки, минимизировав при этом сумму квадратов их длин.

Базовое решение — это следующая динамика:

  • $f[i, j]$ = минимальная стоимость покрытия $i$ первых точек, используя не более $j$ отрезков.
  • Переход — перебор всех возможных последних отрезков, то есть
$$ f[i, j] = \min_{k < i} \{f[k, j-1] + (x_{i-1}-x_k)^2 \} $$

Итоговым ответом будет $f[n, m]$, а суммарно такая динамика будет работать за $O(n^2 m)$.

// x[] — отсортированный массив координат точек, индексация с нуля

// квадрат длины отрезка с i-той до j-той точки
int cost(int i, int j) {
    return (x[j] - x[i]) * (x[j] - x[i]);
}

for (int i = 0; i <= m; i++)
    f[0][k] = 0; // если нам не нужно ничего покрывать, то всё и так хорошо
// все остальные f предполагаем равными бесконечности

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        for (int k = 0; k < i; k++)
            f[i][j] = min(f[i][j], f[k][j - 1] + cost(k, i - 1));

(Заметим, что циклы по i и j можно поменять местами.)

В этой главе мы рассмотрим 4 связанных между собой способа её соптимизировать, помимо непосредственно этой задачи обобщающихся и на многие другие динамики.