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

Материал из Algocode wiki
Перейти к: навигация, поиск

Рассмотрим следующую задачу: Дан массив $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 = \min_{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         add(0, 0);
 4 	for (int i = 1; i <= n; i++) {
 5 		int argmin = get(pref[i]);
 6         dp[i].first = dp[argmin].first + X + pref[i] * pref[i] - 2 * pref[argmin] * pref[i] + pref[argmin] * pref[argmin];
 7         dp[i].second = dp[argmin].second + 1;
 8         add(-2 * pref[i], dp[i] + pref[i] * pref[i])
 9 	}
10 	return dp[n];
11 }
12 /*
13 .
14 .
15 .
16 */
17 
18 int L = -INF;
19 int R = INF;
20 while (L + 1 < R) {
21     int mid = (L + R) / 2;
22 	pair<int, int> X = calc(mid);
23 	if (X.second > k) {
24 		R = mid;
25 	}
26 	else {
27 		L = mid;
28 	}
29 }
30 pair<int, int> res = check(R);
31 cout << res.first - k * R;



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

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