Динамика по подотрезкам

Третий типовой вид: состояние — отрезок массива, переход перебирает точку, в которой отрезок делится надвое.

Признак задачи — операция, которая склеивает или разрезает подряд идущие элементы: скобки, палиндромы, слияния куч, расстановка скобок в произведении.

Порядок обсчёта

Он здесь один и тот же во всех задачах: по возрастанию длины отрезка. Состояние длины $L$ выражается через состояния меньшей длины, значит, к моменту его вычисления они готовы.

for (int len = 2; len <= n; len++)
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        // считаем d[l][r], перебирая точку деления m от l до r-1
    }

Обход по $l$ и $r$ напрямую (двумя вложенными циклами по границам) обычно неверен: при $l$ снаружи и $r$ внутри состояние $d[l][r]$ зависит от $d[l+1][\cdot]$, а строка $l+1$ ещё не посчитана. Либо идите по длине, либо по $l$ вниз, от $n-1$ к нулю.

Склейка куч

В ряд стоят $n$ куч камней. За ход разрешается слить две соседние кучи, стоимость хода — суммарный размер получившейся кучи. Слить всё в одну за наименьшую суммарную стоимость.

Жадность «сливать самые лёгкие соседние» неверна. Контрпример нашёлся перебором: кучи 9, 5, 6, 7. Жадность сливает 5 и 6, потом 11 и 7, и платит 56; оптимум — слить 9 с 5, отдельно 6 с 7, и заплатить 54. На 200 000 случайных наборов до семи куч жадность разошлась с оптимумом в 77 случаях — редко, ровно настолько, чтобы пройти свои тесты и упасть на чужих.

Состояние: $d[l][r]$ — минимальная стоимость слить кучи с $l$ по $r$ в одну.

Переход: последняя склейка объединила левую часть с правой. Переберём место разреза:

$$d[l][r] = \min_{l \le m < r} \big( d[l][m] + d[m+1][r] \big) + \sum_{i=l}^{r} a_i$$

Слагаемое-сумма не зависит от $m$: во сколько бы шагов мы ни сливали, последний ход всегда стоит суммарный вес отрезка. Считается префиксными суммами.

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

flowchart TD
    R["d[l][r], длина 4"]
    R --> A1["d[l][l]"]
    R --> A2["d[l+1][r], длина 3"]
    R --> B1["d[l][l+1], длина 2"]
    R --> B2["d[l+2][r], длина 2"]
    R --> C1["d[l][r-1], длина 3"]
    R --> C2["d[r][r]"]

Три стрелки вниз-влево и три вниз-вправо — это три варианта точки деления. Ни один из потомков не длиннее родителя, поэтому обход по возрастанию длины корректен.

vector<long long> p(n + 1, 0);
for (int i = 0; i < n; i++) p[i + 1] = p[i] + a[i];

vector<vector<long long>> d(n, vector<long long>(n, 0));
for (int len = 2; len <= n; len++)
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        long long best = LLONG_MAX;
        for (int m = l; m < r; m++)
            best = min(best, d[l][m] + d[m + 1][r]);
        d[l][r] = best + p[r + 1] - p[l];
    }
// ответ: d[0][n - 1]

Проверено: на 3000 наборах до семи куч совпадает с перебором всех порядков склейки.

База $d[l][l] = 0$ здесь получается сама — одну кучу сливать не надо, а массив уже заполнен нулями. В задачах на максимум так не выйдет, и базу придётся выписать явно.

Сколько это стоит

Состояний $O(n^2)$, переход перебирает до $n$ точек деления — итого $O(n^3)$. Замер, g++ -O2:

$n$	время
200	1 мс
500	13 мс
1000	137 мс

Отсюда ориентир: до $n \approx 500$ кубическая динамика по подотрезкам проходит спокойно, до 1000–2000 — впритык, дальше нужен другой алгоритм. Ограничение $n \le 500$ в условии почти всегда означает именно её.

Разрезание на палиндромы

Разрезать строку на наименьшее число палиндромов.

Задача решается в два этапа, и это типично: сначала таблица «является ли подстрока палиндромом», потом одномерная динамика по префиксу.

vector<vector<char>> pal(n, vector<char>(n, 0));
for (int l = n - 1; l >= 0; l--)                             // l убывает!
    for (int r = l; r < n; r++)
        pal[l][r] = (s[l] == s[r]) && (r - l < 2 || pal[l + 1][r - 1]);

vector<int> d(n + 1, INT_MAX);
d[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
        if (pal[j][i - 1] && d[j] != INT_MAX)
            d[i] = min(d[i], d[j] + 1);
// число разрезов: d[n] - 1

Проверено: на 3000 строках до 11 символов совпадает с перебором всех способов разрезать строку.

Первая таблица — пример того, как порядок читается из формулы: $pal[l][r]$ зависит от $pal[l+1][r-1]$, значит, $l$ должно убывать, а $r$ — возрастать. Написать оба цикла по возрастанию — и таблица заполнится мусором, причём молча.

Что ещё сюда относится

задача	состояние
оптимальная расстановка скобок в произведении матриц	$d[l][r]$ — минимум умножений
наибольшая палиндромная подпоследовательность	$d[l][r]$ — её длина на отрезке
правильная скобочная последовательность: сколько добавить	$d[l][r]$ — минимум вставок
игра «берут с любого конца»	$d[l][r]$ — разница очков при верной игре
разбиение выпуклого многоугольника на треугольники	$d[l][r]$ — по диагонали

Четвёртая строка — мост к выигрышным позициям: там состояние тоже отрезок, но значение — не стоимость, а исход партии.

А наибольшая палиндромная подпоследовательность имеет короткий обходной путь: это НОП строки с ней же, развёрнутой. Проверено: на 5000 строках до 12 символов перебор, интервальная динамика и НОП с развёрнутой строкой дали один и тот же ответ. Знать оба решения полезно — одно короче писать, другое проще обобщать.