斜率优化小结 前言 没有前言
简介 相较于单调队列优化，斜率优化主要解决以下问题：
对于状态转移中的方程，其中存在某一个多项式同时和两个变量有关。
可以类比数学中线性规划的知识进行求解。
原理概述 对于状态转移方程中的多项式 $val(i,j)$ ，我们首先将其拆开，按照变量种类进行分类。
会出现下面的情况：
将第一类看作常数 $B$，第二类看作因变量 $Y$，第三类进行拆分，将含 $i$的部分连同系数一起看作系数 $K$，将剩下的部分看作自变量 $X$。
经过这样的变换，原转移方程一定可以写成以下形式：
$Y=KX+B$
于是这就是一条直线的解析式。
在 DP 过程中斜率是固定不变的，于是相当于我们在坐标系上平移一条斜率已知的直线，通过令直线经过不同的决策点，从而使答案体现在截距上从而得到答案的解。
决策点集合在坐标系中必然以凸包 形式出现。
图解证明
通过对于凸包各个部分斜率的比较可以确定最优解的出现位置。
同时也可以及时排除不合法或者没有机会成为更优答案的无用节点。
凸包的形式会有两种：
对于答案要求求最大值，需要维护上凸壳。
对于答案要求求最小值，需要维护下凸壳。
这样做是片面 的，还需要结合 $f[i]$ 的符号以及大于小于号来判断。
对于上下凸包的辨别分析应当使用斜率式证明。
斜率式的一般形式：
首先应将方程进行转化，表示为解析式形式。（或者先分析凸包形状再解决式子也是可以的，我倾向于前者）
设 $j_1,j_2$ 为决策点，且 $j_2$ 优于 $j_1$，$0\le j_1<j_2<i$
之后根据题目要求判定两种决策所造成的答案大小关系。
进一步得出一个关于斜率的不等式。
形式如下：
$$k_0\ge\dfrac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}$$
就是说 $j_2$ ，$j_1$ 两个点的斜率如果小于等于直线斜率，那么 $j_2$ 要比 $j_1$ 要优。
对应下凸包。
如果将不等号方向改变，即以下形式：
$$k_0\le \dfrac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}$$
则对应上凸包。
同时每种凸包形式还对应两种不同斜率的直线，同时对应了不同的实现方式（数据结构的使用（其实本质上是思想的不同）。
对于上凸包且直线斜率递减：队头拓展新的决策点，队尾排除不可能选择。使用单调队列。
对于上凸包且直线斜率递增：每次只在队尾操作，使用单调栈。
对于下凸包且直线斜率递减：每次只在队尾操作，使用单调栈。
对于下凸包且直线斜率递增：队头拓展新的决策点，队尾排除不可能选择。使用单调队列。
如何找到最优决策点呢？
考虑暴力，可以在凸包中逐个枚举，对于第一个斜率满足带决策点斜率要求的点，即为我们要求的最佳决策。
更进一步地，由于凸包上点斜率单调，于是可以二分。
对于队列的初始化，一般需要加入初始值。
一般队列的初始化时 head=1,tail=0，之后由于加入了初始值会使 tail++。
对于部分题目，可以通过 head=tail=1 等方式省略初始化。
在求解问题之前首先需要注意单调性问题。
如果 $X$ (即决策点横坐标) 不单调：如果待决策点斜率依然单调的话，显然单调队列就 GG 了，于是需要可以查询前驱后继的东西，可以使用平衡树，CDQ等手段。
若待决策点斜率不单调：如果决策点横坐标依然单调的话，由于不知道最优决策会出现在什么位置，所以队首就不再有用了，这种情况下只能二分。
如果 待决策点斜率与决策点横坐标都不单调：平衡树搞起来！(或者是处理一维之后使用 CDQ)
例题 P3195 [HNOI2008]玩具装箱
满足下凸包且直线斜率递增 。
使用单调队列。
同时使用了 head=tail=1 的技巧来简化初始化。
首先写出转移方程并打出暴力。
for (re int i=1 ;i<=n;i++){for (re int j=0 ;j<i;j++){min (f[i],f[j]+(i-(j+1 )+sum[i]-sum[j]-L)*(i-(j+1 )+sum[i]-sum[j]-L));
之后进行斜率优化。
推导过程：
$$f[i]=min(f[i],f[j]+(i-(j+1)+sum[i]-sum[j]-L)^2)$$
$$f[i]=min(f[i],f[j]+((i+sum[i])-(sum[j]+j+1)-L)^2)$$
$$设\ A[i]=sum[i]+i,B[j]=sum[j]+j+1+L$$
$$f[i]=min(f[i],f[j]+(A[i]-B[j])^2)$$
$$f[i]=min(f[i],f[j]+B[j]^2-2A[i]B[j]+A[i]^2)$$
$$f[i]=f[j]+B[j]^2-2A[i]B[j]+A[i]^2$$
$$2A[i]B[j]+f[i]-A[i]^2=f[j]+B[j]^2$$
$$设\ X=B[j],Y=f[j]+B[j]$$
$$2A[i]B[j]+f[i]-A[i]^2=f[j]+B[j]^2$$
$$Y=2A[i]X+f[i]-A[i]^2$$
代码：
#include <bits/stdc++.h> using namespace std;typedef long long ll;#define re register const int maxn=5e4 +5 ;#define INF 0x3f3f3f3f #define int ll int n,L;double c[maxn],sum[maxn];double f[maxn];int head=1 ,tail=1 ,q[maxn];#define A(x) (sum[x]+x) #define B(x) (sum[x]+x+1+L) #define X(x) B(x) #define Y(x) (f[x]+B(x)*B(x)) inline double pro (int x,int y) return (Y (x)-Y (y))/(X (x)-X (y));inline int read () int x=0 ,f=1 ;char ch=getchar ();while (!isdigit (ch)){if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}return x*f;signed main () #ifdef LawrenceSivan freopen ("aa.in" ,"r" ,stdin);freopen ("aa.out" ,"w" ,stdout);#endif read ();L=read ();for (re int i=1 ;i<=n;i++){scanf ("%lf" ,&c[i]);-1 ]+c[i];for (re int i=1 ;i<=n;i++){while (head<tail&&pro (q[head],q[head+1 ])<2 *A (i))head++;A (i)-B (q[head]))*(A (i)-B (q[head]));while (head<tail&&pro (q[tail-1 ],q[tail])>pro (q[tail-1 ],i))tail--;printf ("%lld\n" ,(ll)f[n]);return 0 ;
P3628 [APIO2010]特别行动队
满足上凸包且斜率递减 。
使用单调队列。
依旧是写出状态转移方程并打出暴力：
for (int i=1 ;i<=n;++i){for (int j=0 ;j<i;++j){max (f[i],f[j]+F (c[i]-c[j]));
斜率优化：
$$f[i]=max(f[i],f[j]+a(sum[i]-sum[j])^2+b(sum[i]-sum[j])+c)$$
$$f[i]=max(f[i],f[j]+asum[i]^2-2asum[i]sum[j]+sum[j]^2+bsum[i]-bsum[j]+c)$$
$$f[i]=max(f[i],f[j]-2asum[i]sum[j]+asum[j]^2-bsum[j])+asum[i]^2+bsum[i]+c$$
$$设\ A[i]=2asum[i],B[j]=f[i]-asum[i]^2-bsum[i]-c$$
$$B(i)=min(f[i],f[j]-A[i]sum[j]+asum[j]^2-bsum[j])$$
$$设\ X(j)=sum[j],Y(j)=f[j]+B[j]^2$$
$$B(i)=min(f[i],f[j]-A[i]X(j)+aX(j)^2-bX(j))$$
$$B(i)=f[j]-A[i]X(j)+aX(j)^2-bX(j)$$
$$Y=f[j]+aX(j)^2-bX(j)$$
$$(Y=A[i]X(j)+B[i])$$
$$f[i]=f[j]-A(i)X(j)+aX(j)^2-bX(j)+asum[i]^2+bsum[i]+c$$
$$求解队头\ f[i]=-A(i)X(j)+Y(j)+aX(i)^2+bX(i)+c$$
代码：
#include <bits/stdc++.h> using namespace std;typedef long long ll;#define INF 0x3f3f3f3f #define re register const int maxn=1e6 +5 ;double f[maxn];double x[maxn],sum[maxn];#define A(x) (a*sum[x]) #define B(x) (f[x]-a*sum[x]*sum[x]-b*sum[x]-c) #define X(x) sum[x] #define Y(x) (f[x]+a*sum[x]*sum[x]-b*sum[x]) inline double pro (int x,int y) return (Y (x)-Y (y))/(X (x)-X (y));inline int read () int x=0 , f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}return x*f;int main () #ifdef LawrenceSivan freopen ("commando.in" , "r" , stdin);freopen ("commando.out" , "w" , stdout);#endif read ();a=read ();b=read ();c=read ();for (re int i=1 ;i<=n;i++){scanf ("%lf" ,&x[i]);-1 ]+x[i];for (re int i=1 ;i<=n;i++){while (head<tail&&pro (q[head],q[head+1 ])>2 *A (i))head++;-2 *A (i)*X (q[head])+Y (q[head])+a*X (i)*X (i)+b*X (i)+c;while (head<tail&&pro (q[tail-1 ],q[tail])<pro (q[tail-1 ],i))tail--;printf ("%lld\n" ,(ll)f[n]);return 0 ;
P5504 [JSOI2011] 柠檬
满足上凸包且直线斜率单调递增 。
使用单调栈。
存在性质：最优情况下，每一段的首尾数字必定相同，而且作为 $s_0$。
需要给每一个点都维护一个独立凸包。
实现可以使用 std::vector.
此题中求 $f[x]$ 时需要把 $x$ 放入凸包中，所以应该先维护凸包，然后把点放进去，之后寻找最优决策点（判断目标斜率），最后求解答案。
方程
$$f[i]=\max\limits_{0<j\le i,s_i=s_j}{f_{j-1}+s_i\times (cnt_i-cnt_j+1)^2}$$
$$f[i]=f_{j-1}+s_i\times (cnt_i-cnt_j+1)^2$$
$$f[i]=f_{j-1}+s_i\times (cnt_i^2-2cnt_icnt_j+2cnt_i+cnt_j^2-2cnt_j+1)$$
$$f[i]=f_{j-1}+s_icnt_i^2-2s_icnt_icnt_j+2s_icnt_i+s_jcnt_j^2-2s_jcnt_j+s_i$$
$$设\ B=f_i-s_icnt_i^2-2s_icnt_i-s_i$$
$$Y=f_{j-1}+s_jcnt_j^2-2s_jcnt_j$$
$$K=2s_icnt_i$$
$$X=cnt_j$$
可以求解。
代码:
#include <bits/stdc++.h> using namespace std;typedef long long ll;#define INF 0x3f3f3f3f #define re register const int maxn=1e5 +5 ;double f[maxn];#define Y(x) (f[x-1]+s[x]*cnt[x]*cnt[x]-2*s[x]*cnt[x]) #define X(x) (cnt[x]) #define K(x) (2*s[x]*cnt[x]) #define B(x) (f[x]-s[x]*cnt[x]*cnt[x]-2*s[x]*cnt[x]-s[x]) inline double slope (int x,int y) return (Y (x)-Y (y))/(X (x)-X (y));inline double calc (int x,int y) return Y (y)-K (x)*X (y)+s[x]*cnt[x]*cnt[x]+2 *s[x]*cnt[x]+s[x];#define top stk[s[i]].size() template <typename T>inline void read (T &x) 0 ;T f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}int main () #ifdef LawrenceSivan freopen ("aa.in" , "r" , stdin);freopen ("aa.out" , "w" , stdout);#endif read (n);for (re int i=1 ;i<=n;i++){read (s[i]);for (re int i=1 ;i<=n;i++){while (top>=2 &&slope (stk[s[i]][top-2 ],stk[s[i]][top-1 ])<slope (stk[s[i]][top-2 ],i))stk[s[i]].pop_back ();push_back (i);while (top>=2 &&calc (i,stk[s[i]][top-1 ])<calc (i,stk[s[i]][top-2 ]))stk[s[i]].pop_back ();calc (i,stk[s[i]][top-1 ]);printf ("%lld\n" ,(ll)f[n]);return 0 ;
P2900 [USACO08MAR]Land Acquisition G
好题！
需要以下结论：
由于我们需要的代价是最长的乘以最宽的，所以对我们来说我们只关心这两个极值，其他的一概不管。
于是考虑这样几种情况：
所以可以发现，对于任意的一整段，我们只关心其中长度最长的，宽度最宽的两个（或者一个），考虑把这些地排成一个序列。
把最高的放最左边，最宽的放最右边。
这样就可以构成一个长度递减但是宽度递增的序列了。
夹在中间的长不如最长的长，宽不如最长的宽的那几个就没啥用了。
对于一段区间，可以考虑拆开买，于是总贡献就是前半部分加上后半部分。
由此列出转移方程：
$$f_i=min{f_j+h_{j+1}\times w_i }$$
解释: $f_j$ 是表示买 $[1,j]$ 这个区间需要的代价，$h_{j+1}\times w_i$ 是后半段的代价。由于长度降序排序，宽度升序排序，所以拆分位置下一位必然是最高的，即 $h_{j+1}$ ，整个区间的右端点一定是最宽的，即 $w_i$ 。
发现包含一个与 $i,j$ 都有关的多项式。
考虑斜率优化：
$$f_i=min{f_j+h_{j+1}\times w_i }$$
$$f_i=f_j+h_{j+1}\times w_i$$
$$B=f_i$$
$$Y=f_j$$
$$K=w_i$$
$$X=h_{j+1}$$
$$B=Y+KX$$
$$Y=-KX+B$$
不是我刻意水，这个斜率优化就这么简单
注意一下虽然题目要我们求最小值，但是这个可不是下凸包哦。
推导过程（使用斜率式）：
设 $j_1,j_2$ 为决策点，且 $j_2$ 优于 $j_1$，$0\le j_1<j_2<i$
则 $f_2+h_{j_2+1}w_i\le f_1+h_{j_1+1}w_i$
移项得到 $w_i(h_{j_2+1}-h_{j_1+1})\le f_{j_1}-f_{j_2}$
由高度降序可得 $h_{j_2+1}<h_{j_1+1}$
于是除过去变号。
即：$w_i\ge \dfrac {f_{j_1}-f_{j_2}}{(h_{j_2+1}-h_{j_1+1})}$
调整分母符号得：
即：$-w_i\le \dfrac {f_{j_1}-f_{j_2}}{(h_{j_1+1}-h_{j_2+1})}$
所以斜率递减。维护上凸包
复杂度瓶颈在于排序
代码：
#include <bits/stdc++.h> using namespace std;typedef long long ll;typedef unsigned long long ull;#define INF 0x3f3f3f3f #define re register const int maxn=1e5 +5 ;int n,num;double f[maxn];#define mp make_pair #define B(x) (f[x]) #define X(x) (a[x+1].first) #define Y(x) (f[x]) #define K(x) (a[x].second) inline double slope (int x,int y) return (Y (x)-Y (y))/(X (x)-X (y));template <typename T>inline void read (T &x) 0 ;T f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}int main () #ifdef LawrenceSivan freopen ("aa.in" , "r" , stdin);freopen ("aa.out" , "w" , stdout);#endif read (n);for (re int i=1 ;i<=n;i++){read (a[i].first);read (a[i].second);sort (a+1 ,a+1 +n);reverse (a+1 ,a+1 +n);for (re int i=1 ;i<=n;i++){if (a[i].second>a[head].second)a[++head]=a[i];1 ;for (re int i=1 ;i<=n;i++){while (head<tail&&slope (q[head],q[head+1 ])>-K (i))head++;K (i)*X (q[head])+Y (q[head]);while (head<tail&&slope (q[tail-1 ],q[tail])<slope (q[tail-1 ],i))tail--;printf ("%lld\n" ,(ll)f[n]);return 0 ;
CF311B Cats Transport
这个玩意太坑啦！！！！
调了一整个上午+下午的 1h ，最后求助了大家才明白怎么回事。
最后脑子都不转了。
首先考虑一个人出发后，会有一部分猫在等待。
如果到达某一个点的时候不能够恰好接到一只猫，那么肯定是不优的，他完全可以早走一会然后让猫少等一会。
于是这启示我们应该注意一只猫恰好被接到的时间。
如果想要恰好接到需要满足在 $A_i$ 出发
$$A_i=T_i-\sum\limits_{j=1}^{H_j}D_j$$
所以出发时间若为 $t$ ，那么这只猫的等待时间就是 $t-A_i$.
设 $f[i,j]$ 表示 $i$ 个人带走了 $j$ 只猫所用的代价。
方程
$$f[i,j]=min{f[i-1][k]+\sum\limits_{p=k+1}^{j}A_j-A_p}$$
$$f[i,j]=min{f[i-1][k]+(j-k)A_j-\sum\limits_{p=k+1}^{j}A_p }$$
$$f[i,j]=min{f[i-1][k]+(j-k)A_j-S[j]+S[k] }$$
$$f[i,j]=f[i-1][k]+(j-k)A_j-S[j]+S[k] $$
$$f[i,j]=f[i-1][k]+j\times A_j-k\times A_j-S[j]+S[k] $$
$$设\ B=f[i,j]-j\times A_j+S[j]$$
$$Y=f[i-1][k]+S[k]$$
$$X=k$$
$$K=A[j]$$
$$Y=KX+B$$
$$设\ k_2\ 优于\ k_1\ 且k_2>k_1。$$
$$f[i - 1][k_1] + sum[k_1] - A[j] * k_1 > f[i - 1][k_2] + sum[k_2] - A[j] * k_2$$
$$Y(k_1)-Kk_1>Y(k_2)-Kk_2$$
$$(k_1-k_2)K<Y(k_1)-Y(k_2)$$
$$K>\dfrac{Y(k_1)-Y(k_2)}{k_1-k_2}$$
满足下凸包，且直线斜率递增
使用单调队列。
但是这个题有及其坑爹的地方！
如果横坐标相等的话斜率就不存在了（或者可以理解为斜率无穷大）
然后我们平常写的 slope 就 GG 了。
如何解决呢？
把分母乘过去，不要写成斜率形式就好啦。
代码：
#include <bits/stdc++.h> using namespace std;typedef long long ll;#define INF 0x3f3f3f3f #define re register const int maxn=2e5 +5 ;105 ][maxn],ans=INF;1 ,tail=0 ;#define Y(x) (f[i-1][x]+sum[x]) #define X(x) (x) #define K(x) (A[x]) #define B(x) (f[i][x]-x*A[x]+sum[x]) inline double slope (int x,int y) return 1.0 *(Y (x)-Y (y))/(X (x)-X (y));inline ll read () 0 , f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}return x*f;int main () #ifdef LawrenceSivan freopen ("aa.in" , "r" , stdin);freopen ("aa.out" , "w" , stdout);#endif read ();m=read ();p=read ();for (re int i=2 ;i<=n;i++){-1 ]+read ();for (re int i=1 ;i<=m;i++){read ();T[i]=read ();sort (A+1 ,A+1 +m);for (re int i=1 ;i<=m;i++){-1 ]+A[i];memset (f,0x3f ,sizeof (f));0 ][0 ]=0 ;for (re int i=1 ;i<=p;i++){1 ;tail=0 ;q[++tail]=0 ;for (re int j=1 ;j<=m;j++){while (head<tail&&Y (q[head])-Y (q[head+1 ])>K (j)*(q[head]-q[head+1 ]))head++;Y (q[head])+A[j]*(j-q[head])-sum[j];while (head<tail&&(Y (j)-Y (q[tail-1 ]))*(q[tail]-q[tail-1 ])<(Y (q[tail])-Y (q[tail-1 ]))*(j-q[tail-1 ]))tail--;printf ("%lld\n" ,f[p][m]);return 0 ;
P3648 [APIO2014]序列分割
根据题意很容易可以列出方程：
设 $F[i,j]$ 表示当前处理到第 $i$ 位，分了 $j$ 次。
$$F[i,k]=\max\limits_{0\le j<i}{F[j,k-1]+val(j+1,i) }$$
其中
$$val(j+1,i) =(sum(i)-sum(j))\times sum(j)$$
去掉 $\max$ 得到：
$$F[i,k]=F[j,k-1]+(sum(i)-sum(j))\times sum(j)$$
为了方便可以将 $F[i,k]$ 暂且看作 $f[i]$ ，把 $F[j,k-1]$ 暂且看作 $f[j]$
得到：
$$f[i]=f[j]+sum(i)\times sum(j)-sum(j)^2$$
$$设\ B=f[i]$$
$$Y=f[j]-sum(j)^2$$
$$K=-sum(i)$$
$$X=sum(j)$$
直线斜率单调递减。
设决策点 $k_2$ 优于 $k_1$ 且 $k_2>k_1$，
根据方程可以发现：
$$f[k_2]+sun(i)\times sum(k_2)-sum(k_2)^2\ge f[k_1]+sun(i)\times sum(k_1)-sum(k_1)^2$$
$$即\ Y(k_2)-KX(k_2)\ge Y(k_1)-KX(k_1)$$
通过移项可以得到：
$$KX(k_1)-KX(k_2)\ge Y(k_1)-Y(k_2)$$
$$K(X(k_1)-X(k_2))\ge Y(k_1)-Y(k_2)$$
$$K\le \dfrac{Y(k_1)-Y(k_2)}{X(k_1)-X(k_2)}$$
上凸包。
满足上凸包且直线斜率单调递减。
使用单调队列。
通过这道题，我们可以发现：$f$ 数组千万不要开 double ！！！
否则你会最后一个点 WA 的很惨！！！
另外一个需要注意的点就是横坐标相等的情况。
直接取斜率为 -INF 就行了。
#include <bits/stdc++.h> using namespace std;typedef long long ll;typedef unsigned long long ull;#define INF 0x3f3f3f3f3f3f3f3f #define re register const int maxn=1e5 +5 ;1 ,tail=0 ;300 ];#define B(x) (f[i]) #define X(x) (sum[x]) #define Y(x) (g[x]-sum[x]*sum[x]) #define K(x) (-sum[x]) inline double slope (ll x,ll y) return X (x)==X (y)?-INF:1.0 *((Y (x)-Y (y))*1.0 )/((X (x)-X (y))*1.0 );template <typename T>inline void read (T &x) 0 ;T f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}int main () #ifdef LawrenceSivan freopen ("aa.in" , "r" , stdin);freopen ("aa.out" , "w" , stdout);#endif read (n),read (k);for (re int i=1 ;i<=n;i++){read (a[i]);-1 ]+a[i];for (re int tim=1 ;tim<=k;tim++){1 ,tail=0 ;0 ;memcpy (g,f,sizeof (g));for (re int i=1 ;i<=n;i++){while (head<tail&&slope (q[head],q[head+1 ])>=K (i))head++;while (head<tail&&slope (q[tail-1 ],q[tail])<=slope (q[tail-1 ],i))tail--;printf ("%lld\n" ,f[n]);int i=k,j=n;while (pre[j][i]){printf ("%lld " ,pre[j][i]);return 0 ;
自然是可以通过写成相乘形式来避免这种问题的。
注意要带等号，否则会 WA
for (re int i=1 ;i<=n;i++){while (head<tail&&Y (q[head])-Y (q[head+1 ])<=K (i)*(X (q[head])-X (q[head+1 ])))head++;while (head<tail&&(Y (q[tail-1 ])-Y (q[tail]))*(X (q[tail-1 ])-X (i))<=(Y (q[tail-1 ])-Y (i))*(X (q[tail-1 ])-X (q[tail])))tail--;
P4027 [NOI2007] 货币兑换
设 $f[i]$ 表示在第 $i$ 天卖掉所有的金券所获得的最大收益。
容易得到：
$$f[i]=max{f[i-1],num_A\times A[i]+num_B\times B[i]}$$
发现只与我们手中剩下的金券数量有关。
于是回去考虑我们什么时候获得的金券。
假设在第 $j$ 天买到了金券，而上一次卖是在第 $k$ 天，于是可以写出：
$$f[k]=num_A\times A[j]+num_B\times B[j]$$
用 $rate$ 把 $num_A$ 进行转换：
$$f[k]=num_B\times R[j]\times A[j]+num_B\times B[j]$$
移项得到：
$$num_B=\dfrac{f[k]}{R[j]\times A[j]+B[j]}$$
同时得到：
$$num_A=\dfrac{f[k]\times R[j]}{R[j]\times A[j]+B[j]}$$
于是至此可以把方程写出来：
$$f[i]=max{\dfrac{f[k]\times R[j]}{R[j]\times A[j]+B[j]}\times A[i]+\dfrac{f[k]}{R[j]\times A[j]+B[j]}\times B[i]}$$
然后这就是 $\mathcal{O(n^2)}$ 的了。
cin>>n>>f[0 ];for (int i=1 ;i<=n;++i)cin>>A[i]>>B[i]>>R[i];1 ]=f[0 ]*R[1 ]/(A[1 ]*R[1 ]+B[1 ]);for (int i=2 ;i<=n;++i)for (int j=1 ;j<i;++j)max (ans,f[j]*A[i]+f[j]/R[j]*B[i]);printf ("%.3lf\n" ,ans);
考虑进一步优化。
之后去掉 $max$
$$f[i]=\dfrac{f[k]\times R[j]}{R[j]\times A[j]+B[j]}\times A[i]+\dfrac{f[k]}{R[j]\times A[j]+B[j]}\times B[i]$$
发现式子很丑，于是我们还是看原来的式子吧。。。
$$f[i]=num_A\times A[i]+num_B\times B[i]$$
通过上面的研究可以发现，$num$ 这两项中 $i,j$ 是捆绑在一起的，存在交叉项。
考虑斜率优化。
两边同时除以 $B[i]$：
$$\dfrac{f[i]}{B[i]}=num_A\times \dfrac{A[i]}{B[i]}+num_B$$
移项：
$$num_B =-\dfrac{A[i]}{B[i]}\times num_A +\dfrac{f[i]}{B[i]}$$
这里的转化和以往的转化不大一样，并不只是单纯按照变量种类进行分类，而是适当根据题目进行了调整。
设 $x[i]=num_A,y[i]=num_B,k=-A[i]/B[i]$
设决策点 $j,k$ ，满足 并且 $j$ 优于 $k$：
$$x[j]A[i]+y[j]B[i]>x[k]A[i]+y[k]B[i]$$
$$(x[j]-x[k])\times A[i]>-(y[j]-y[k])\times B[i]$$
$$-\dfrac{A[i]}{B[i]}<\dfrac{y[j]-y[k]}{x[j]-x[k]}$$
发现对应了一个上凸包。
并且同时横坐标不严格单调递增，并且直线斜率也不是单调的，所以需要动态维护凸包，或者采取 CDQ 分治的手段。
平衡树和 CDQ 都是可以的。
分别说一下：
CDQ 做法：
常规的斜率优化是需要满足横坐标与斜率都要单调的，于是可以考虑排序后处理。
可以发现，斜率再输入之后其实就是固定的，所以我们可以首先按照斜率排序。
发现天数变成了乱序，所以需要对天数进行分治。
对于 CDQ 解决 DP 问题，我们需要首先递归左区间，然后处理左区间对右区间的影响，再递归右区间。
考虑如何处理影响。
每次处理影响之前都已经处理好左区间了，所以现在不需要管左区间的顺序。所以对于左区间，我们对它进行任何顺序的调换都不会有影响。
由于我们需要构建凸包，所以需要保证 $x$ 的有序。
索性左区间直接按照横坐标排序，使用单调栈构建凸包即可。
由于右区间斜率已经递减 ，所以直接使用单调队列 更新答案即可。
在分治边界还需要处理一下 $f[l]=\max(f[l],f[l-1])$。
值得注意的是，对于上面提到的对左区间按照横坐标排序，如果直接使用快速排序的话，那么复杂度为 $\mathcal{O(n\log^2 n)}$。
稍加调整就可以做到 $\mathcal{O(n\log n)}$。
CDQ 分治本身就是归并的过程，所以直接在处理完右区间之后，进行一次归并排序即可。
处理完右区间之后再归并是为了保证左区间按照横坐标有序，右区间按照斜率有序。
#include <bits/stdc++.h> using namespace std;typedef long long ll;typedef unsigned long long ull;#define INF 0x3f3f3f3f #define re register const int maxn=1e5 +5 ;const double eps=1e-9 ;int n;double f[maxn];double A[maxn],B[maxn],R[maxn];struct node {double x,y;int id;inline bool operator < (const node &a)const {return -(A[id]/B[id])>-(A[a.id]/B[a.id]);inline double slope (int x,int y) if (q[x].x==q[y].x)return -INF;return (q[x].y-q[y].y)/(q[x].x-q[y].x);int stk[maxn];#define K(x) (-A[x]/B[x]) void cdq (int l,int r) if (l==r){max (f[l],f[l-1 ]);return ;int mid=(l+r)>>1 ,lp=l,rp=mid+1 ,tot=l;for (re int i=l;i<=r;i++){if (q[i].id<=mid)t[lp++]=q[i];else t[rp++]=q[i];for (re int i=l;i<=r;i++){cdq (l,mid);int top=0 ,ptr=1 ;for (re int i=l;i<=mid;i++){while (top>=2 &&slope (stk[top],i)>slope (stk[top-1 ],stk[top]))top--;for (re int i=mid+1 ;i<=r;i++){while (ptr<top&&slope (stk[ptr],stk[ptr+1 ])>K (q[i].id))ptr++;max (f[q[i].id],q[stk[ptr]].x*A[q[i].id]+q[stk[ptr]].y*B[q[i].id]);cdq (mid+1 ,r);+1 ,tot=l;while (lp<=mid&&rp<=r){if (q[lp].x<q[rp].x)t[tot++]=q[lp++];else t[tot++]=q[rp++];while (lp<=mid)t[tot++]=q[lp++];while (rp<=r)t[tot++]=q[rp++];for (re int i=l;i<=r;i++)q[i]=t[i];namespace IO{template <typename T> inline void read (T &x) {0 ;T f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}template <typename T, typename ... Args>inline void read (T& t, Args&... args) read (t); read (args...);template <typename T> void write (T x) {if (x<0 )putchar ('-' ),x=-x;if (x>9 )write (x/10 );putchar (x%10 +'0' );template <typename T,typename ... Args> void write (T t,Args... args) {write (t);putchar (' ' );write (args...);using namespace IO;signed main () #ifdef LawrenceSivan freopen ("aa.in" ,"r" , stdin);freopen ("aa.out" ,"w" , stdout);#endif read (n);scanf ("%lf" ,&f[0 ]);for (re int i=1 ;i<=n;i++){scanf ("%lf%lf%lf" ,&A[i],&B[i],&R[i]);0 ]/(A[i]*R[i]+B[i])*R[i],f[0 ]/(A[i]*R[i]+B[i]),i};0 ];sort (q+1 ,q+1 +n);cdq (1 ,n);printf ("%.3lf\n" ,f[n]);return 0 ;
平衡树做法：
需要维护两个东西 $lk[],rk[]$ ，分别代表每一个点左侧的直线的斜率和右侧的直线的斜率。
其实过程就是这样的：
现在有一个凸包，我们需要插入一个新的节点。
一定要注意精度。
eps 给不等号朝向的一侧。
更新状态时直接找到第一个大于当前直线斜率的位置更新即可。
#include <bits/stdc++.h> using namespace std;typedef long long ll;typedef unsigned long long ull;#define INF 0x3f3f3f3f #define re register const int maxn=1e5 +5 ;const double eps=1e-9 ;int n;double f[maxn],A[maxn],B[maxn],R[maxn];double lk[maxn],rk[maxn];double X[maxn],Y[maxn];namespace Splay{int c[maxn][2 ],fa[maxn],val[maxn],rt,tot;#define ls(x) c[x][0] #define rs(x) c[x][1] inline int dir (int x) return x==ls (fa[x])?0 :1 ;inline void set (int x,int px,int d) inline void rotate (int x) int d=!dir (x),f=fa[x];set (c[x][d],f,!d);set (x,fa[f],dir (f));set (f,x,d);inline void splay (int x,int goal) for (;fa[x]!=goal;rotate (x))if (fa[fa[x]]!=goal)rotate (dir (x)^dir (fa[x])?x:fa[x]);if (goal==0 )rt=x;inline double slope (int x,int y) if (fabs (X[x]-X[y])<eps)return -INF;return (Y[x]-Y[y])/(X[x]-X[y]);inline int Pre (int x) int s=ls (x),u=x;while (s)if (slope (s,x)<=lk[s]+eps)u=s,s=rs (s);else s=ls (s);return u;inline int Nxt (int x) int s=rs (x),u=x;while (s)if (slope (x,s)+eps>=rk[s])u=s,s=ls (s);else s=rs (s);return u;inline int find (double num) int u=rt;while (true ){if (!u)return 0 ;if (lk[u]+eps>=num&&rk[u]<=num+eps)return u;else if (lk[u]+eps<num)u=ls (u);else u=rs (u);inline void update (int x) splay (x,0 );if (ls (x)){int l=Pre (x);splay (l,x);rs (l)=0 ;slope (l,x);else lk[x]=INF;if (rs (x)){int r=Nxt (x);splay (r,x);ls (r)=0 ;slope (x,r);else rk[x]=-INF;if (lk[x]<=rk[x]+eps){ls (x),rs (rt)=rs (x),fa[rs (x)]=rt,fa[rt]=0 ;rs (rt)]=slope (rt,rs (rt));inline void insert (int &x,int last,int id) if (!x){return ;if (X[id]<=X[x]+eps)insert (ls (x),x,id);else insert (rs (x),x,id);using namespace Splay;namespace IO{template <typename T> inline void read (T &x) {0 ;T f=1 ;char ch=getchar ();while (!isdigit (ch)) {if (ch=='-' )f=-1 ;ch=getchar ();}while (isdigit (ch)){x=x*10 +(ch^48 );ch=getchar ();}template <typename T, typename ... Args>inline void read (T& t, Args&... args) read (t); read (args...);template <typename T> void write (T x) {if (x<0 )putchar ('-' ),x=-x;if (x>9 )write (x/10 );putchar (x%10 +'0' );template <typename T,typename ... Args> void write (T t,Args... args) {write (t);putchar (' ' );write (args...);using namespace IO;signed main () #ifdef LawrenceSivan freopen ("aa.in" ,"r" , stdin);freopen ("aa.out" ,"w" , stdout);#endif read (n);scanf ("%lf" ,&f[0 ]);for (re int i=1 ;i<=n;i++){scanf ("%lf%lf%lf" ,&A[i],&B[i],&R[i]);int j=find (-A[i]/B[i]);max (f[i-1 ],X[j]*A[i]+Y[j]*B[i]);insert (rt,0 ,i); update (i);printf ("%.3lf\n" ,f[n]);return 0 ;
后记 天坑到这里就算是填完了，期待着下一个天坑的填补 /kk
