DP по связным компонентам
DP по связным компонентам
JOI 2016 — Небоскрёб
Условие задачи
Даны , посчитайте количество перестановок этих чисел таких, что
DP по связным компонентам
Даны , посчитайте количество перестановок этих чисел таких, что
где — заданное целое число.
Отсортируем массив и будем вставлять элементы в порядке возрастания.
Мы строим перестановку в порядке значений, а не по позициям.
При вставке элементов мы отслеживаем, сколько связных компонент заполненных позиций сейчас существует.
Пример частичной перестановки: 1, 2, ?, ?, 3, ?, 5, ?
Здесь:
[1,2], [3], [5] → 3 компонентыТакая точка зрения позволяет рассуждать о том, как вставка следующего значения меняет и структуру, и стоимость.
Пусть
— количество способов после вставки первых наименьших элементов таких, что:
? равны )При вставке мы рассматриваем все структурные эффекты на компоненты:
Эти действия изменяют:
Ключевой трюк — как мы эффективно поддерживаем стоимость при поэтапной вставке.
Перед вставкой все пустые позиции (?) считаются имеющими значение .
Поскольку значения вставляются в отсортированном порядке, это даёт минимально возможную стоимость, согласованную с текущей структурой.
Когда действительно вставляется, все оптимистичные значения становятся реальными.
Каждая соседняя пара, включающая ?, увеличивается на
Поэтому суммарная стоимость увеличивается на
Каждая связная компонента даёт два граничных ребра. Занятые концы убирают по одной границе каждый.
Итак:
Следовательно:
Из состояния после обновления стоимости:
Слить две компоненты
Присоединить внутри компоненты
Создать новую компоненту
Создать новый конец (если )
Продлить до конца (если )
int solve(int idx, int components, int cost, int filled_ends) {
if (filled_ends > 2 || cost > L) return 0;
if (components == 0 && idx > 1) return 0;
if (idx == n + 1) return filled_ends == 2 && components == 1;
int &ret = dp[idx][components][cost][filled_ends];
if (ret != -1) return ret;
int new_cost = cost + (a[idx] - a[idx - 1]) * (2 * components - filled_ends);
long long ans = 0;
if (components >= 2)
ans += (components - 1) *
solve(idx + 1, components - 1, new_cost, filled_ends);
if (components >= 1)
ans += (2 * components - filled_ends) *
solve(idx + 1, components, new_cost, filled_ends);
ans += (components + 1 - filled_ends) *
solve(idx + 1, components + 1, new_cost, filled_ends);
if (filled_ends < 2) {
ans += (2 - filled_ends) *
solve(idx + 1, components + 1, new_cost, filled_ends + 1);
ans += (2 - filled_ends) *
solve(idx + 1, components, new_cost, filled_ends + 1);
}
return ret = ans;
}