http://www.lydsy.com/JudgeOnline/problem.php?id=1492 (题目链接)
题意
两种金券，金券按照比例交易：买入时，将投入的资金购买比例为$rate[i]$的两种金券；卖出时，卖出持有一定比例的金券。已知未来$n$天金券的价格$A[i],B[i]$，初始资金为$S$，求最大获利。
Solution
首先根据贪心的思想，每次买入和卖出一定是花光了所有的资金和卖掉了所有的金券。$f[i]$表示第$i$天的最大获利，那么转移分两种情况，在这天卖出和不在这一天卖出，在一天卖出我们枚举上一次在哪一天买入金券：
\begin{aligned} f[i]=MAX\{MAX\{\frac{f[j]}{rate[j]*A[j]+B[j]}*rate[j]*A[i]+\frac{f[j]}{rate[j]*A[j]+B[j]}*B[i]\},f[i-1]\} \end{aligned}
这很显然是个斜率的式子：
\begin{aligned} X[j]&=\frac{f[j]*rate[j]}{rate[j]*A[j]+B[j]} \\ Y[j]&=\frac{f[j]}{rate[j]*A[j]+B[j]} \end{aligned}
但是横坐标和斜率都不单调，所以我们使用CDQ分治。每次先处理$[l,mid]$位置的$f$，然后再用这些$f$构凸包去更新$[mid+1,r]$位置的$f$。
代码膜PoPoQQQ
细节
横坐标相等
代码
// bzoj1492
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<30)
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=100010;
double f[maxn];
int n,st[maxn];
struct data {double A,B,rate,k;int pos;}q[maxn],nq[maxn];
struct point {double x,y;}p[maxn],np[maxn]; bool cmp(data a,data b) {return a.k<b.k;}
double slope(point a,point b) {
return a.x==b.x ? inf*(a.y>b.y ? 1 : -1) : (a.y-b.y)/(a.x-b.x);
}
void solve(int l,int r) {
if (l==r) {
f[l]=max(f[l],f[l-1]);
p[l].x=f[l]/(q[l].A+q[l].B/q[l].rate);
p[l].y=f[l]/(q[l].A*q[l].rate+q[l].B);
return;
}
int mid=(l+r)>>1,l1=l,l2=mid+1,top=0;
for (int i=l;i<=r;i++) q[i].pos<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i];
for (int i=l;i<=r;i++) q[i]=nq[i];
solve(l,mid);
for (int i=l;i<=mid;i++) {
while (top>1 && slope(p[st[top-1]],p[st[top]])<slope(p[st[top]],p[i])) top--;
st[++top]=i;
}
for (int i=mid+1;i<=r;i++) {
while (top>1 && slope(p[st[top-1]],p[st[top]])<q[i].k) top--;
f[q[i].pos]=max(f[q[i].pos],q[i].A*p[st[top]].x+q[i].B*p[st[top]].y);
}
solve(mid+1,r);
for (int i=l,j=mid+1,k=l;i<=mid || j<=r;) {
if (j>r || (i<=mid && p[i].x<p[j].x)) np[k++]=p[i++];
else np[k++]=p[j++];
}
for (int i=l;i<=r;i++) p[i]=np[i];
}
int main() {
scanf("%d%lf",&n,&f[0]);
for (int i=1;i<=n;i++) {
scanf("%lf%lf%lf",&q[i].A,&q[i].B,&q[i].rate);
q[i].k=-q[i].A/q[i].B;
q[i].pos=i;
}
sort(q+1,q+1+n,cmp);//先按照斜率排序常数会小很多
solve(1,n);
printf("%.3lf",f[n]);
return 0;
}