Лямбда-оптимизация

Рассмотрим следующую задачу: Дан массив $a_1, a_2, \dots, a_n$. Надо разбить его на $k$ отрезков так, чтобы минимизировать сумму квадратов сумм отрезков, $k \le n$.

Сведем задачу к другой — вместо того, чтобы набирать $k$ отрезков, придумаем разбиение на сколько-нибудь отрезков, но за каждый отрезок будем добавлять к функции ответа штраф, равный $\lambda$. Пусть для $\lambda_1$ количество отрезков в разбиении равно $k_1$. Тогда для $\lambda_2 > \lambda_1$ $k_2 \ge k_1$. Интуиция у этого факта такая — если мы за каждый отрезок платим меньше, то мы можем взять больше отрезков. Понятно, что если данное неравенство не выполняется, то лямбда-оптимизация не работает.

Поскольку зависимость между $k$ и $\lambda$ монотонная, то можно сделать бинарный поиск по $\lambda$ и найти такую, при которой $k_\lambda=k$. Новую задачу можно решать при помощи convex hull trick, потому что $$dp_i = \max_{j=1}^{i-1} dp[j] + \lambda + pref_i^2 - (2 \cdot pref_j) \cdot pref_i + pref_j^2$$, где $pref$ — массив префиксных сумм.

 1 pair<int, int> calc(int X) {
 2 	vector<pair<int, int>> dp(n + 1);
 3 	for (int i = 1; i <= n; i++) {
 4 		dp[i] = f(i);
 5 	}
 6 	return dp[n];
 7 }
 8 /*
 9 .
10 .
11 .
12 */
13 
14 int L = -INF;
15 int R = INF;
16 while (L + 1 < R) {
17     int mid = (L + R) / 2;
18 	pair<int, int> X = calc(mid);
19 	if (X.second > k) {
20 		R = mid;
21 	}
22 	else {
23 		L = mid;
24 	}
25 }
26 pair<int, int> res = check(R);
27 cout << res.first - k * R;
28 ...

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s