浅谈斜率优化

浅谈斜率优化

概论

列出状态转移方程，如果能化简为以下的形式：

\[dp=\min/\max(c+d[j]+C)\]
此时我们就可以利用单调队列优化从做 \(O(n^2)\) 到 \(O(n)\) 的复杂度。
现在考虑更一般的情况，如果化简为以下形式：

\[dp=\min/\max(a\cdot b[j]+c+d[j]+C)\]
此时单调队列优化就不再适用，就需要使用斜率优化。
斜率优化的思想就是通过剔除一些不可能成为最优解的决策点，使剩下的决策点形成一个凸包，再使用单调队列、二分、平衡树、CDQ 分治或者李超线段树来快速转移。
理论讲解

斜率优化有两种理解方式：
代数法

设决策点 \(j_2\) 优于 \(j_1\)。
则有：（\(\) 对应 \(\min\)）

\[a\cdot b[j_1]+c+d[j_1]+Ca\cdot b[j_2]+c+d[j_2]+C\]
化简得：

\[a\cdot b[j_1]+d[j_1]a\cdot b[j_2]+d[j_2]\]
令 \(Y(x)=-d[x]\)，\(X(x)=b[x]\)，\(k=a\)，再让 \(X(j_2)>X(j_1)\)。
移项得（不等号要变号）：

\[k>/> f;                t = t[i - 1] + t;                f = f[i - 1] + f;        }        memset(dp, 0x7f, sizeof dp);        dp[0] = 0;        for (int i = 1; i > s;        for (int i = 1; i > t >> c;                t += t[i - 1];                c += c[i - 1];        }        int hh = 0, tt = 0;        q[0] = 0;        for (int i = 1; i > s;        for (int i = 1; i > t >> c;                t += t[i - 1];                c += c[i - 1];        }        int hh = 0, tt = 0;        q[0] = 0;        for (int i = 1; i > 1;                        if (dp[q[mid + 1]] - dp[q[mid]] > (t + s) * (c[q[mid + 1]] - c[q[mid]]))                        {                                r = mid;                        }                        else                        {                                l = mid + 1;                        }                }                dp = dp[q[r]] + t * (c - c[q[r]]) + s * (c[n] - c[q[r]]);                while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]) * (c - c[q[tt]]) >= (dp - dp[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))                {                        tt--;                }                q[++tt] = i;        }        cout  n;        for (int i = 1; i > h;        }        for (int i = 1; i > w;                w = w + w[i - 1];        }        p[1].k = -2 * h[1], p[1].b = h[1] * h[1] - w[1];        t.update(1, 1, M, 1);        for (int i = 2; i > m;        for (int i = 1; i > a;                a += a[i - 1];                dp[1] = 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[1].insert(0);        for (int i = 1; i