Формулировка задачи
Иногда нам нужно вычислить для каждой позиции оптимальное значение функции вида
Иногда нам нужно вычислить для каждой позиции оптимальное значение функции вида
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
где выбор удовлетворяет
То есть для каждой позиции мы хотим найти наилучшее значение .
Пусть opt(i) обозначает значение , которое даёт оптимальный ответ для позиции .
Если выполняется следующее условие монотонности:
то мы можем применить оптимизацию «Разделяй и властвуй».
Это означает, что по мере увеличения оптимальный выбор никогда не уменьшается.
Мы определяем рекурсивную функцию
которая вычисляет ответы для всех позиций
при предположении, что
Идея такова:
opt(m), проверив всех кандидатовopt(m) известно, рекурсивно решить:
[opt_l, opt(m)][opt(m), opt_r]Из-за монотонности оптимальных выборов эти границы корректны.
Каждый уровень рекурсии обрабатывает все проверки кандидатов для непересекающегося набора позиций, а глубина рекурсии логарифмическая.
В результате общее число вычислений функции часто равно
умноженному на стоимость вычисления одного перехода.
solve(l, r, opt_l, opt_r)
void solve(int l, int r, int opt_l, int opt_r) {
if (l > r) {
return;
}
int m = (l + r) / 2;
int opt_m = opt_l;
auto best_f = f(m, opt_l);
for (int j = opt_l + 1; j <= opt_r; j++) {
auto cur = f(m, j);
if (cur > best_f) {
best_f = cur;
opt_m = j;
}
}
res[m] = best_f;
opt[m] = opt_m;
solve(l, m - 1, opt_l, opt_m);
solve(m + 1, r, opt_m, opt_r);
}