浅谈斜率优化

33333mm

浅谈斜率优化

概论

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

\[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\)。
则有：（\(<\) 对应 \(\max\)，\(>\) 对应 \(\min\)）

\[a\cdot b[j_1]+c+d[j_1]+C</>a\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</>\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\]

这就是说，将两个决策点在平面直角坐标系中用两点表示出来，如果两点间斜率小于（或大于）\(k\)，那么后面的点优于前面的点。
现在我们考虑有如下位置关系的三个点：
[attach]https://free4.yunpng.top/2025/02/04/67a181a6a0aab.png[/attach]
如图，\(k_2<k_1\)。
下面我们讨论 \(\max\) 的情况。

• 当 \(k<k_2<k_1\) 时，则 \(C\) 比 \(A\) 优，\(B\) 比 \(C\) 优，\(B\) 最优。
  
• 当 \(k_2\le k\le k_1\) 时，则 \(A\)、\(B\) 至少有一个比 \(C\) 优。
  
• 当 \(k_2<k_1<k\) 时，则 \(A\) 比 \(C\) 优，\(C\) 比 \(B\) 优，\(A\) 最优。
  

综上，无论何种情况，\(C\) 都不可能最优，可以删去。
推广以上的性质，对于所有的决策点：
[attach]https://free4.yunpng.top/2025/02/04/67a184879df24.png[/attach]
删去所有不可能为最优的决策点，发现可能为最优解的点会形成如下的一个下凸包：
[attach]https://free4.yunpng.top/2025/02/04/67a185f8d8147.png[/attach]
同理，对于 \(\min\) 的情况，会形成一个上凸包。
几何法

我们先讨论 \(\max\) 的情况：

\[dp=\max(a\cdot b[j]+c+d[j]+C)\]

去掉 \(\max\)，再移项得：

\[-d[j]=a\cdot b[j]+c-dp+C\]

我们可以将 \(-d[j]\) 看作纵坐标，\(a\) 看作斜率，\(b[j]\) 看作横坐标，\(c-dp+C\) 看作常数。
那么此时就可以把状态转移方程看作一个形如 \(y=kx+b\) 的直线方程，其中对于同一个 \(i\) 斜率 \(k=a\) 是不变的。
要使 \(dp\) 最大，就要使方程的截距 \(b\) 尽可能小。
将所有决策点 \((b[j],-d[j])\) 在平面直角坐标系中表示出来：
[attach]https://free4.yunpng.top/2025/02/04/67a184879df24.png[/attach]
寻找最优决策点的过程就可以看作平移一条斜率不变的直线，自下往上遇到的第一个点必然使截距最小，如图：
[attach]https://free4.yunpng.top/2025/02/04/67a18a86e340d.png[/attach]
事实上，这个点就是和前面点斜率小于等于当前斜率，和后面点斜率大于等于当前斜率的点。
现在我们考虑改变直线斜率，发现可能是最优解的决策点当且仅当在下面的下凸包上：
[attach]https://free4.yunpng.top/2025/02/04/67a185f8d8147.png[/attach]
不在下面的下凸包上的，无论斜率如何改变，都不可能是从下往上平移最小的点。
同理，对于 \(\min\) 的情况，会形成一个上凸包。
个人更喜欢几何法，比较直观，所以下面的例题都会采用几何法论证。
代码实现

对于不同的情况，我们有不同的插入决策点及查询最优解的方式（具体的可以看下面的例题）：
决策点横坐标（\(b[j]\)）严格增，直线方程斜率（\(a\)）严格增

• 插入：可以维护一个队列存储决策点编号 \(j\)，由于决策点横坐标（\(b[j]\)）严格增，再根据凸包斜率严格增（或减）的性质，在插入时只要队列倒数第二元素和队尾的斜率小于（或大于）队尾和要插入的点的斜率，就弹出队尾，直到保证斜率严格增（或减）。
  
• 查询：根据最优决策点和前面点斜率小于（或大于）等于当前斜率，和后面点斜率大于（或小于）等于当前斜率的点，再根据直线方程斜率（\(a\)）严格增，所以最优决策点横坐标严格增，不用保存前面的决策点，因此只要队首的两个元素斜率小于（或大于）当前斜率，就弹出队首，直到不能弹为止，队首就是最优决策点。
  
• 复杂度：\(O(n)\)。
  

决策点横坐标（\(b[j]\)）严格增，直线方程斜率（\(a\)）不严格增

• 插入：由于决策点横坐标（\(b[j]\)）严格增不变，同上。
  
• 查询：由于直线方程斜率（\(a\)）不严格增，所以最优决策点没有单调性了，此时只能根据凸包斜率的单调性二分找到和前面点斜率小于（或大于）等于当前斜率，和后面点斜率大于（或小于）等于当前斜率的点的点。
  
• 复杂度：\(O(n\log n)\)。
  

决策点横坐标（\(b[j]\)）不严格增

由于横坐标都不严格增，也就是说可能加的点在两点之间，上面的方法就行不通了。
可以考虑利用动态维护凸包或者采用 CDQ 分治离线等方法，在此先不予陈述。
这里介绍一种思维含量低、代码量小、常数小的优秀算法：李超线段树。
事实上，李超线段树并不是维护动态凸包，而是利用本身的特性直接维护答案。
将一些不变量提出：

\[dp=c+C+\min/\max(b[j]\cdot a+d[j])\]

我们将 \(\min/\max\) 中的式子看作一个直线方程 \(y=kx+b\)，其中 \(b[j]\) 是斜率，\(a\) 是此时横坐标，\(d[j]\) 是截距。
发现此时就是要求若干个直线 \(y=b[j]\cdot x+d[j]\) 在 \(x=a\) 时的最值，而这恰好是李超线段树所维护的东西。
因此，每次我们只需将直线 \(y=b[j]\cdot x+d[j]\) 插入李超树，再查询所有直线在 \(x=a\) 时的最值更新答案即可。
时间复杂度：\(O(n\log n)\)。
例题

P5785 [SDOI2012] 任务安排 link

题目描述

机器上有 \(n\) 个需要处理的任务，它们构成了一个序列。这些任务被标号为 \(1\) 到 \(n\)，因此序列的排列为 \(1 , 2 , 3 \cdots n\)。这 \(n\) 个任务被分成若干批，每批包含相邻的若干任务。从时刻 \(0\) 开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间是 \(T_i\)。在每批任务开始前，机器需要启动时间 \(s\)，而完成这批任务所需的时间是各个任务需要时间的总和。
注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 \(C_i\)。
请确定一个分组方案，使得总费用最小。
数据范围

\(T1:1\leq n \leq 5000,0\leq S\leq 50,1\leq T_i,C_i \leq 100\)
\(T2:1\leq n \leq 300000,0\leq S\leq 512,1\leq T_i,C_i \leq 100\)
\(T3:1\leq n \leq 300000,0\leq S\leq 512,0\leq C_i \leq 512,-512\leq T_i \leq 512\)
解题思路

\(T1:\)
朴素 DP，不需要优化。
我们对 \(c\) 和 \(t\) 做前缀和，用前缀和替代原来的数组。

• 状态表示：\(dp\) 表示完成前 \(i\) 个任务的最小费用。
  
• 初始化：\(dp[0]=0\)。
  
• 状态转移：考虑分配成的最后一组，设最后一组为 \(j+1\sim i\)，首先要在 \(dp[j]\) 的基础上加上 \(t \cdot (c - c[j])\)，但是 \(s\) 貌似比较难处理，发现 \(s\) 会对后面所有的任务产生影响，因此为方便处理，我们可以提前把它对后面的总贡献 \(s \cdot (c[n] - c[j])\) 直接算进当前区间，因此有状态转移方程：
  \[dp = \min(dp[j] + t \cdot (c - c[j]) + s \cdot (c[n] - c[j]))\]
  
  
• 答案：\(dp[n]\)。
  

时间复杂度：\(O(n^2)\)。
\(T2：\)
因为 \(1\leq n \leq 300000\)，\(O(n^2)\) 无法通过，发现状态转移方程符合斜率优化的条件，考虑斜率优化。
化简、移项得：

\[dp[j] = (t+s)\cdot c[j]+dp-t\cdot c[j]-s\cdot c[n]\]

要使 \(dp\) 更小，那么就要使截距尽可能小，因此决策点会形成一个下凸包。
由于 \(T_i,C_i \geq 1\)，因此前缀和严格增，所以横坐标 \(c[j]\) 严格增，截距 \(t+s\) 严格增，应用第一种情况即可。
\(T3：\)
此时 \(-512\leq T_i \leq 512\)，所以截距不严格增，其他不变，在查询时二分找决策点即可。
编码技巧：在处理斜率时为避免误差，可以写作乘积的形式。
代码

\(T1：\)
#include<bits/stdc++.h>#define endl "\n"#define ll long longusing namespace std;const int N = 5010;int n, s;ll t[N], f[N];ll dp[N];int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        cin >> n >> s;        for (int i = 1; i <= n; i++)        {                cin >> t >> f;                t = t[i - 1] + t;                f = f[i - 1] + f;        }        memset(dp, 0x7f, sizeof dp);        dp[0] = 0;        for (int i = 1; i <= n; i++)        {                for (int j = 0; j < i; j++)                {                        dp = min(dp, dp[j] + t * (f - f[j]) + s * (f[n] - f[j]));                }        }        cout << dp[n] << endl;        return 0;}\(T2：\)
#include<bits/stdc++.h>#define endl "\n"using namespace std;const int N = 3e5 + 10;int n, s;int t[N], c[N];int dp[N], q[N];int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        cin >> n >> s;        for (int i = 1; i <= n; i++)        {                cin >> t >> c;                t += t[i - 1];                c += c[i - 1];        }        int hh = 0, tt = 0;        q[0] = 0;        for (int i = 1; i <= n; i++)        {                while (hh < tt && (dp[q[hh + 1]] - dp[q[hh]]) <= (t + s) * (c[q[hh + 1]] - c[q[hh]]))                {                        hh++;                }                dp = dp[q[hh]] + t * (c - c[q[hh]]) + s * (c[n] - c[q[hh]]);                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 << dp[n] << endl;        return 0;}\(T3：\)
#include<bits/stdc++.h>#define endl "\n"#define ll long longusing namespace std;const int N = 3e5 + 10;int n, s;ll t[N], c[N];ll dp[N], q[N];int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        cin >> n >> s;        for (int i = 1; i <= n; i++)        {                cin >> t >> c;                t += t[i - 1];                c += c[i - 1];        }        int hh = 0, tt = 0;        q[0] = 0;        for (int i = 1; i <= n; i++)        {                int l = hh, r = tt;                while (l < r)                {                        int mid = (l + r) >> 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 << dp[n] << endl;        return 0;}P4655 [CEOI 2017] Building Bridges link

题目描述

有 \(n\) 根柱子依次排列，每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\)。
现在想要建造若干座桥，如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间，那么需要 \((h_i-h_j)^2\)​​ 的代价。
在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)，注意 \(w_i\) 不一定非负，因为可能政府希望拆除某些柱子。
现在政府想要知道，通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。
数据范围

\(2\le n\le 10^5,0\le h_i,\vert w_i\vert\le 10^6\)。
解题思路

先用 \(w\) 的前缀和替代原来的序列。
考虑先列出 \(O(n^2)\) 的状态转移方程：

• 状态表示：\(dp\) 表示用桥梁把前 \(i\) 根柱子连接的最小代价。
  
• 初始化：\(dp[1]=0\)
  
• 状态转移：考虑柱子 \(i\) 和 \(j\) 相接，则有：
  \[dp=\min(dp[j]+(h-h[j])^2+w[i-1]-w[j])\]
  
  
• 答案：\(dp[n]\)。
  

现在考虑斜率优化，移项：

\[dp[j]=2hh[j]-h[j]^2-w[j]+dp-h^2+w[i-1]\]

发现由于原来的 \(h\) 可以为 \(0\)，因此横坐标 \(h[j]\) 不严格增，只能用李超线段树优化。
将式子化为：

\[dp=h^2+w[i-1]+\min(-2h[j]h+dp[j]+h[j]^2-w[j])\]

问题转化为：每次插入直线 \(y=-2h[j]\cdot x+dp[j]+h[j]^2-w[j]\)，求在 \(x=h\) 时的最小值。
用李超线段树维护即可，时间复杂度 \(O(n\log n)\)。
代码

#include<bits/stdc++.h>#define endl "\n"using namespace std;const int N = 1e5 + 10, M = 1e6 + 10;int n;long long h[N], w[N];long long dp[N];struct line{        long long k, b;                inline long long calc(long long x)        {                return k * (x - 1) + b;        }} p[N];struct SGT{        #define ls x << 1        #define rs x << 1 | 1        #define mid ((l + r) >> 1)        int dat[M << 2];                void update(int x, int l, int r, int k)        {                if (!dat[x])                {                        dat[x] = k;                        return;                }                if (p[k].calc(mid) < p[dat[x]].calc(mid))                {                        swap(k, dat[x]);                }                if (p[k].calc(l) < p[dat[x]].calc(l))                {                        update(ls, l, mid, k);                }                if (p[k].calc(r) < p[dat[x]].calc(r))                {                        update(rs, mid + 1, r, k);                }        }                long long query(int x, int l, int r, int k)        {                if (r < k || l > k)                {                        return 1e18;                }                long long res = p[dat[x]].calc(k);                if (l == r)                {                        return res;                }                return min(res, min(query(ls, l, mid, k), query(rs, mid + 1, r, k)));        }} t;int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        p[0].b = 1e18;        cin >> n;        for (int i = 1; i <= n; i++)        {                cin >> h;        }        for (int i = 1; i <= n; i++)        {                cin >> 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 <= n; i++)        {                dp = h * h + w[i - 1] + t.query(1, 1, M, h + 1);                p.k = -2 * h, p.b = dp + h * h - w;                t.update(1, 1, M, i);        }        cout << dp[n] << endl;        return 0;}P4072 [SDOI2016] 征途 link

题目描述

Pine 开始了从 \(S\) 地到 \(T\) 地的征途。
从 \(S\) 地到 \(T\) 地的路可以划分成 \(n\) 段，相邻两段路的分界点设有休息站。
Pine 计划用 \(m\) 天到达 \(T\) 地。除第 \(m\) 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。
设方差是 \(v\)，可以证明，\(v\times m^2\) 是一个整数。为了避免精度误差，输出结果时输出 \(v\times m^2\)。
数据范围

\(1 \le n \le 3000\)。
保证从 \(S\) 到 \(T\) 的总路程不超过 \(3\times 10^4\)。
\(2 \leq m \leq n+1\)，每段路的长度为不超过 \(3 \times 10^4\) 的正整数。
解题思路

考虑先化简最后答案的式子（\(a\) 表示输入的每段路的长度）：

\[s^2=\frac{(\bar a-a_1)^2+(\bar a-a_2)^2+\cdots+(\bar a-a_m)^2}{m}\]


\[s^2=\frac{m\bar a^2-2\bar a(a_1+a_2+\cdots+a_m)+a_1^2+a_2^2+\cdots+a_m^2}{m}\]


\[s^2=\frac{m(\frac{\sum_{i=1}^ma_i}{m})^2-2(\frac{\sum_{i=1}^ma_i}{m})(\sum_{i=1}^ma_i)+\sum_{i=1}^ma_i^2}{m}\]


\[s^2=-\frac{{(\sum_{i=1}^ma_i)}^2}{m^2}+\frac{\sum_{i=1}^ma_i^2}{m}\]


\[s^2\cdot m^2={-(\sum_{i=1}^ma_i)}^2+m\sum_{i=1}^ma_i^2\]

发现右边第一项是定值，因此只要右边第二项最小即可，也就是问题转化为求最小平方和。
不妨用 \(a\) 的前缀和替代原来的序列。
于是开始动态规划：

• 状态表示：由于分成几段也会影响答案，因此要开两维表示，\(dp[j]\) 表示前 \(i\) 项分成 \(j\) 段的最小平方和。
  
• 初始化：\(dp[0]=0\)。
  
• 状态转移：设最后一段为 \(k+1\sim i\)，则有：
  \[dp[j]=\min(dp[k][j-1]+(a-a[k])^2)\]
  
  
• 答案：把 \(dp[n][m]\) 代入上面的式子即可。
  

时间复杂度 \(O(n^3)\)，无法通过，考虑斜率优化。
将式子化为：

\[dp[k][j-1]+a[k]^2=2aa[k]+dp[j]-a^2\]

要使 \(dp[j]\) 更小，则截距就要更小，所以最优决策点组成一个下凸包。
由于 \(a\) 严格增，所以横坐标和斜率都严格增，应用第一种情况即可。
比较值得注意的是，因为这道题是二维的，我们优化的是第一维，所以可以先枚举第二维，然后跑 \(m\) 遍斜率优化。
时间复杂度 \(O(m\log n)\)。
代码

#include<bits/stdc++.h>#define endl "\n"#define ll long longusing namespace std;const int N = 3e3 + 10;ll n, m;ll a[N];ll dp[N][N], q[N];int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        cin >> n >> m;        for (int i = 1; i <= n; i++)        {                cin >> a;                a += a[i - 1];                dp[1] = a * a;        }        for (int j = 2; j <= m; j++)        {                int h = 0, t = 0;                q[0] = 0;                for (int i = 1; i <= n; i++)                {                        while (h < t && (dp[q[h + 1]][j - 1] - dp[q[h]][j - 1] + a[q[h + 1]] * a[q[h + 1]] - a[q[h]] * a[q[h]]) <= 2 * a * (a[q[h + 1]] - a[q[h]]))                        {                                h++;                        }                        dp[j] = dp[q[h]][j - 1] + (a - a[q[h]]) * (a - a[q[h]]);                        while (h < t && (dp[q[t]][j - 1] + a[q[t]] * a[q[t]] - dp[q[t - 1]][j - 1] - a[q[t - 1]] * a[q[t - 1]]) * (a - a[q[t]]) >= (dp[j - 1] + a * a - dp[q[t]][j - 1] - a[q[t]] * a[q[t]]) * (a[q[t]] - a[q[t - 1]]))                        {                                t--;                        }                        q[++t] = i;                }        }        cout << m * dp[n][m] - a[n] * a[n] << endl;        return 0;}P4027 [NOI2007] 货币兑换 link

题目描述

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 \(K\) 天中 A 券和 B 券的价值分别为 \(A_K\) 和 \(B_K\)（元/单位金券）。
为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。
比例交易法分为两个方面：
a)  卖出金券：顾客提供一个 \([0, 100]\) 内的实数 \(OP\) 作为卖出比例，其意义为：将 \(OP\%\) 的 A 券和 \(OP\%\) 的 B 券以当时的价值兑换为人民币；
b)  买入金券：顾客支付 \(IP\) 元人民币，交易所将会兑换给用户总价值为 \(IP\) 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 \(K\) 天恰好为 \(\mathrm{Rate}_ K\)；
例如，假定接下来 \(3\) 天内的 \(A_K,B_K,\mathrm{Rate}_ K\) 的变化分别为：
时间\(A_K\)\(B_K\)\(\mathrm{Rate}_ K\)第一天\(1\)\(1\)\(1\)第二天\(1\)\(2\)\(2\)第三天\(2\)\(2\)\(3\)假定在第一天时，用户手中有 \(100\) 元人民币但是没有任何金券。
用户可以执行以下的操作：
时间用户操作人民币(元)A 券的数量B 券的数量开户无\(100\)\(0\)\(0\)第一天买入 \(100\) 元\(0\)\(50\)\(50\)第二天卖出 \(50\%\)\(75\)\(25\)\(25\)第二天买入 \(60\) 元\(15\)\(55\)\(40\)第三天卖出 \(100\%\)\(205\)\(0\)\(0\)注意到，同一天内可以进行多次操作。
小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 \(N\) 天内的 A 券和 B 券的价值以及 \(\mathrm{Rate}\)。他还希望能够计算出来，如果开始时拥有 \(S\) 元钱，那么 \(N\) 天后最多能够获得多少元钱。
数据范围

\(N \le 10^5\)，\(0 < A_K \leq 10\)，\(0 < B_K\le 10\)，\(0 < \mathrm{Rate}_K \le 100\)，\(\mathrm{MaxProfit}  \leq 10^9\)。
必然存在一种最优的买卖方案满足：
每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。
解题思路

考虑 DP。

• 状态表示：\(dp\) 表示前 \(i\) 天最多能获得多少钱。
  
• 初始化：\(dp[0]=S\)。
  
• 状态转移：设现在是第 \(i\) 天，要使钱最多那么一定不买金券。
  
  
  
  • 不卖金券：\(dp=dp[i-1]\)。
    
  • 卖金券：设现在卖出的金券是在第 \(j\) 天买入的，如果卖出有利润，那么当时就应该花光所有钱买金券以获得最大收益。
    设第 \(i\) 天最多能获得 \(x_i\) 张 \(A\) 券， \(y_i\) 张 \(B\) 券，则有：
    
    \[x_i=dp_i\frac{R_i}{A_iR_i+B_i}\]
    
    
    \[y_i=dp_i\frac{1}{A_iR_i+B_i}\]
    
    所以：\(dp=\max(x_jA_i+y_jB_i)\)。
    
  综上，状态转移方程为：
  
  \[dp=\max(dp[i-1],\max(x_jA_i+y_jB_i))\]
  
  
  
• 答案：\(dp[n]\)。
  

现在来考虑斜率优化，我们把它化成斜率优化能处理的式子（先不考虑不卖，最后把它算上即可）：

\[y_j=-\frac{A_i}{B_i}x_j+\frac{1}{B_i}dp\]

发现 \(x_j\) 没有单调性，因此考虑使用李超线段树。
变形得：

\[dp=b\max(x_j\frac{a_i}{b_i}+y_j)\]

问题转化为：每次插入直线 \(y=x_j\cdot x+y_j\)，求在 \(x=\frac{a_i}{b_i}\) 时的最大值。
用李超线段树维护即可，时间复杂度 \(O(n\log n)\)。
值得注意的是，这道题需要查询实数位置的最小值，可以离散化，再将李超线段树的 clac() 函数改写即可。
代码

#include<bits/stdc++.h>#define endl "\n"using namespace std;const int N = 1e5 + 10;const double eps = 1e-10;int n;double a[N], b[N], c[N], d[N], r[N];double ans;struct line{        double k, b;        int id;                inline double calc(int x)        {                return k * c[x] + b;        }} p[N];struct SGT{        #define ls x << 1        #define rs x << 1 | 1        #define mid ((l + r) >> 1)        int dat[N << 2];                void update(int x, int l, int r, int k)        {                if (!dat[x])                {                        dat[x] = k;                        return;                }                if (p[k].calc(mid) - p[dat[x]].calc(mid) > eps)                {                        swap(k, dat[x]);                }                if (p[k].calc(l) - p[dat[x]].calc(l) > eps || (p[k].calc(l) == p[dat[x]].calc(l) && k < dat[x]))                {                        update(ls, l, mid, k);                }                if (p[k].calc(r) - p[dat[x]].calc(r) > eps || (p[k].calc(r) == p[dat[x]].calc(r) && k < dat[x]))                {                        update(rs, mid + 1, r, k);                }        }                double query(int x, int l, int r, int k)        {                if (r < k || l > k)                {                        return 0;                }                double res = p[dat[x]].calc(k);                if (l == r)                {                        return res;                }                return max(res, max(query(ls, l, mid, k), query(rs, mid + 1, r, k)));        }} t;int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        cin >> n >> ans;        for (int i = 1; i <= n; i++)        {                cin >> a >> b >> r;                c = d = a / b;        }        sort(c + 1, c + n + 1);        for (int i = 1; i <= n; i++)        {                int sum = lower_bound(c + 1, c + n + 1, d) - c;                ans = max(ans, b * t.query(1, 1, n, sum));                p.k = ans * r / (a * r + b), p.b = ans / (a * r + b);                t.update(1, 1, n, i);        }        cout << fixed << setprecision(3) << ans << endl;        return 0;}