浅谈斜率优化
浅谈斜率优化概论
列出状态转移方程，如果能化简为以下的形式：
\=\min/\max(c+d+C)\]
此时我们就可以利用单调队列优化从做 \(O(n^2)\) 到 \(O(n)\) 的复杂度。
现在考虑更一般的情况，如果化简为以下形式：
\=\min/\max(a\cdot b+c+d+C)\]
此时单调队列优化就不再适用，就需要使用斜率优化。
斜率优化的思想就是通过剔除一些不可能成为最优解的决策点，使剩下的决策点形成一个凸包，再使用单调队列、二分、平衡树、CDQ 分治或者李超线段树来快速转移。
理论讲解
斜率优化有两种理解方式：
代数法
设决策点 \(j_2\) 优于 \(j_1\)。
则有：（\(\) 对应 \(\min\)）
\\cdot b+c+d+Ca\cdot b+c+d+C\]
化简得：
\\cdot b+da\cdot b+d\]
令 \(Y(x)=-d\)，\(X(x)=b\)，\(k=a\)，再让 \(X(j_2)>X(j_1)\)。
移项得（不等号要变号）：
\; t = t + t; f = f + f; } memset(dp, 0x7f, sizeof dp); dp = 0; for (int i = 1; i > s; for (int i = 1; i > t >> c; t += t; c += c; } int hh = 0, tt = 0; q = 0; for (int i = 1; i > s; for (int i = 1; i > t >> c; t += t; c += c; } int hh = 0, tt = 0; q = 0; for (int i = 1; i > 1; if (dp] - dp] > (t + s) * (c] - c])) { r = mid; } else { l = mid + 1; } } dp = dp] + t * (c - c]) + s * (c - c]); while (hh < tt && (dp] - dp]) * (c - c]) >= (dp - dp]) * (c] - c])) { tt--; } q[++tt] = i; } coutn; for (int i = 1; i > h; } for (int i = 1; i > w; w = w + w; } p.k = -2 * h, p.b = h * h - w; t.update(1, 1, M, 1); for (int i = 2; i > m; for (int i = 1; i > a; a += a; dp = a * a; } for (int j = 2; j > n >> ans; for (int i = 1; i > a >> b >> r; c = d = a / b; } sort(c + 1, c + n + 1); for (int i = 1; i > m >> a >> b >> c; for (int i = 1; i > tr.x >> tr.y >> tr.p >> tr.q; } sort(tr + 1, tr + m + 1, cmp); q.insert(0); for (int i = 1; i
页:
[1]