Problem Statement
Sometimes we need to compute, for every position , the optimal value of a function of the form
Sometimes we need to compute, for every position , the optimal value of a function of the form
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
where the choice of satisfies
So for each position , we want to find the best value of .
Let opt(i) denote the value of that gives the optimal answer for position .
If the following monotonicity condition holds:
then we can apply Divide and Conquer Optimization.
This means that as increases, the optimal choice of never decreases.
We define a recursive function
which computes the answers for all positions
under the assumption that
The idea is:
opt(m) by checking all candidatesopt(m) is known, recursively solve:
[opt_l, opt(m)][opt(m), opt_r]Because of the monotonicity of the optimal choices, these bounds are correct.
Each level of recursion processes all candidate checks for a disjoint set of positions, and the recursion depth is logarithmic.
As a result, the total number of evaluations of the function is often
times the cost of evaluating one transition.
Note: Sometimes, in the implementation you might need extra requirement on , or .
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);
}