Лямбда-оптимизация: различия между версиями
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
Строка 39: | Строка 39: | ||
pair<int, int> res = check(R); | pair<int, int> res = check(R); | ||
cout << res.first - k * R; | cout << res.first - k * R; | ||
− | |||
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Версия 14:17, 27 сентября 2019
Рассмотрим следующую задачу: Дан массив $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[j] * pref[j];
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