http://www.lydsy.com/JudgeOnline/problem.php?id=1492
（题目描述太长了不粘贴了……）
………………………………………………………
我
是自己做的
抄开心
的
……………………………………………………………
所以……emm，简单的dp就是：
f(i)=max(a[i]*x[j]+b[i]*y[j])
其中x和y表示在第i 天，用最多的钱能够换成的A券和B券。
完后……这怎么斜率优化啊……如果把x和y看做点来斜率优化的话它们也没有单调性啊。
推荐一个博客，可以在这里看推导式子（其实是我懒）：http://blog.csdn.net/lych_cys/article/details/50674962
平衡树固然可以解决问题，但是CDQ分治在这种问题上显得更加睿智。
我们完全可以对其变成一维排a/b，二维CDQ一下它们出现时间t，三维求f。把每个点看做询问和添加操作即可。
剩下的就是单调队列基础操作了。
（题解瞎编完了hhh）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double dl;
const int N=1e5+;
struct node{
dl x,y;
inline bool operator <(const node &b)const{
return x<b.x||x==b.x&&y<b.y;
}
}p[N],que[N];
int n,t[N],tmp[N];
dl f[N],a[N],b[N],rate[N],ans;
inline bool cmp(int x,int y){
return a[x]*b[y]<a[y]*b[x];
}
inline bool slope(node k,node j,node i){
return (j.x-i.x)*(k.y-i.y)-(j.y-i.y)*(k.x-i.x)<=;
}
inline dl suan(node j,int i){
return j.x*a[i]+j.y*b[i];
}
void cdq(int l,int r){
if(l==r){
f[l]=max(f[l],f[l-]);
ans=max(ans,f[l]);
p[l].y=f[l]/(a[l]*rate[l]+b[l]);
p[l].x=p[l].y*rate[l];
return;
}
int mid=(l+r)>>,idx1=l,idx2=mid+,ql=,qr=;
for(int i=l;i<=r;i++){
if(t[i]<=mid)tmp[idx1++]=t[i];
else tmp[idx2++]=t[i];
}
for(int i=l;i<=r;i++)t[i]=tmp[i];
cdq(l,mid);
for(int i=l;i<=mid;i++){
while(qr>&&slope(que[qr-],que[qr],p[i]))qr--;
que[++qr]=p[i];
}
for(int i=mid+;i<=r;i++){
int j=t[i];
while(ql<qr&&suan(que[ql],j)<=suan(que[ql+],j))ql++;
f[j]=max(f[j],suan(que[ql],j));
}
cdq(mid+,r);
if(l==&&r==n)return;
ql=l,idx1=l,idx2=mid+;
while(ql<=r){
if(idx2>r||idx1<=mid&&p[idx1]<p[idx2])que[ql++]=p[idx1++];
else que[ql++]=p[idx2++];
}
for(int i=l;i<=r;i++)p[i]=que[i];
return;
}
int main(){
scanf("%d%lf",&n,&f[]);
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
t[i]=i;
}
sort(t+,t+n+,cmp);
cdq(,n);
printf("%.3lf\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++