Aliens trick (lambda-оптимизация): как убрать ограничение «ровно k групп» из ДП?
В задаче надо разбить массив ровно на k частей с минимальной стоимостью. ДП с явным измерением по числу частей dp[i][j] это O(n²·k) или хотя бы O(n·k) — не лезет по времени/памяти при больших k. Слышал про «aliens trick». В чём идея и когда он работает?
2 ответа
Aliens trick (он же lambda-оптимизация / Lagrangian relaxation) убирает жёсткое измерение «ровно k групп». Идея: вместо того чтобы насильно держать ровно k частей, добавляем штраф λ за каждую новую часть и решаем ДП без ограничения на число частей — оно становится одномерным и быстрым. При фиксированном λ оптимальное решение использует какое-то число частей cnt(λ). Функция «оптимальная стоимость от числа частей» выпукла, поэтому cnt(λ) монотонна по λ: больше штраф → меньше частей. Бинпоиском по λ находим такое значение, при котором решение использует ровно k частей, и вычитаем суммарный штраф λ·k.
// solve(lambda) возвращает {минимальная_стоимость_со_штрафом, число_частей}
pair<long long,int> solve(long long lambda) {
// одномерное ДП: dp[i] = min_j(dp[j] + cost(j,i) + lambda), cnt[i] = ...
// (за O(n) или O(n log n) c CHT/монотонной очередью)
}
long long lo = 0, hi = BIG, ans = 0;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
auto [cost, parts] = solve(mid);
if (parts >= k) { ans = cost - mid * k; lo = mid + 1; }
else hi = mid - 1;
}
Сложность O(log(range) · T), где T — стоимость одного ДП без ограничения. Условие применимости — выпуклость зависимости «стоимость от k»; без неё бинпоиск по λ не сходится к нужному k.
Две практические грабли. Первая — целочисленный λ и плато: при оптимальном λ число частей может «скакать» через k (несколько разбиений дают одну и ту же стоимость со штрафом). Тогда выбирают λ так, чтобы cnt >= k при минимальном λ, и используют, что на плато стоимость линейна — формула cost - λ·k всё равно даёт верный ответ. Вторая — при равенстве в ДП-переходе предпочитай вариант с большим числом частей (тай-брейк), чтобы cnt(λ) была корректно монотонна и бинпоиск нашёл ровно k. Без аккуратного тай-брейка ловишь WA на тестах с равными стоимостями.