标签：CDQ分治，凸包，DP
题目
题目传送门
Description
小Y最近在一家金券交易所工作。
该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下简称B券）。
每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。
我们记录第 K 天中 A券 和 B券 的价值分别为 AK 和 BK（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。
比例交易法分为两个方面：
（a）卖出金券：顾客提供一个 [0,100] 内的实数 OP 作为卖出比例，其意义为：将 OP% 的 A券和 OP% 的 B券 以当时的价值兑换为人民币；
（b）买入金券：顾客支付 IP 元人民币，交易所将会兑换给用户总价值为 IP 的金券，并且，满足提供给顾客的A券和B券的比例在第 K 天恰好为 RateK；
例如，假定接下来 3 天内的 Ak、Bk、RateK 的变化分别为： 假定在第一天时，用户手中有 100元 人民币但是没有任何金券。
用户可以执行以下的操作： 注意到，同一天内可以进行多次操作。
小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来N天内的A券和B券的价值以及Rate。
他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能够获得多少元钱。
输入第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。
接下来N行，第K行三个实数AK、BK、RateK，意义如题目中所述。
对于100%的测试数据，满足：0
Output
只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。
3 100
1 1 1
1 2 2
2 2 3
Sample Output
225.000
HINT
输入文件可能很大，请采用快速的读入方式。必然存在一种最优的买卖方案满足： 每次买进操作使用完所有的人民币； 每次卖出操作卖出所有的金券。
题意
有AB两种货币，每天可以可以付Pi元，买到A券和B券，且A:B=Ratei，也可以卖掉OPi%的A券和B券，每天AB价值为Ai和Bi。开始有S元，n天后手中不能有AB券，问最大获益。
分析
显示O(n^2)DP
设f[i]表示前i天的最大收益
第i天将手中的钱全部换掉，可以换成的A券数目X(i)：
f[i]∗Rate[i]Rate[i]∗A[i]+B[i]
f
[
i
]
∗
R
a
t
e
[
i
]
R
a
t
e
[
i
]
∗
A
[
i
]
+
B
[
i
]
第i天将手中的钱全部换掉，可以换成的B券数目Y(i)：
f[i]∗1Rate[i]∗A[i]+B[i]
f
[
i
]
∗
1
R
a
t
e
[
i
]
∗
A
[
i
]
+
B
[
i
]
第i天将第j天的AB券全部卖掉：
A[i]∗X(j)+B[i]∗Y(j)
A
[
i
]
∗
X
(
j
)
+
B
[
i
]
∗
Y
(
j
)
则状态转移方程为
f[i]=max(f[i−1],A[i]∗X(j)+B[i]∗Y(j))
f
[
i
]
=
m
a
x
(
f
[
i
−
1
]
,
A
[
i
]
∗
X
(
j
)
+
B
[
i
]
∗
Y
(
j
)
)
那么我们需要求
max(p=A[i]∗X(j)+B[i]∗Y(j))
m
a
x
(
p
=
A
[
i
]
∗
X
(
j
)
+
B
[
i
]
∗
Y
(
j
)
)
转化为直线方程
Y(j)=−A[i]B[i]∗X(j)+pB[i]
Y
(
j
)
=
−
A
[
i
]
B
[
i
]
∗
X
(
j
)
+
p
B
[
i
]
使这条直线的截距最大
设X(j) < X(k)，当k比j更优时需要满足
slop(j,k)>−A[i]B[i]
s
l
o
p
(
j
,
k
)
>
−
A
[
i
]
B
[
i
]
因为X(i)可能不是单调的，所以不能够用单调队列来维护，我们这里需要维护一个凸壳
然后就用到了CDQ分治（第一次写，膜了黄学长代码qwq）
CDQ分治大题思想就是进行左区间的分治时考虑对右区间的影响
按照时间轴分治，把每天看成一个点，首先将所有点按照斜率排序
并且保证操作结束后按照x,y升序排列
具体步骤代码里有详细注释
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
#define eps 1e-6
using namespace std;
inline ll read(){
ll f=
1,x=
0;
char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=getchar();}
return x*f;
}
const int maxn=
1e5+
6;
int n,top,
stack[maxn];
double f[maxn];
struct point{
double x,y,a,b,k,rate;
int w,id;}p[maxn],t[maxn];
inline double getk(
int a,
int b){
if(!b)
return -inf;
if(
fabs(p[a].x-p[b].x)<eps)
return inf;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
inline bool operator < (point a,point b){
return a.k>b.k;}
void solve(
int l,
int r){
if(l==r){
f[l]=max(f[l],f[l-
1]);
p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
p[l].x=p[l].rate*p[l].y;
return;
}
int l1=l,mid=(l+r)>>
1,l2=mid+
1,j=
1;
rep(i,l,r)
if(p[i].id<=mid)t[l1++]=p[i];
else t[l2++]=p[i];
rep(i,l,r)p[i]=t[i];
solve(l,mid);
top=
0;
rep(i,l,mid){
while(top>
1&&getk(
stack[top-
1],
stack[top])<getk(
stack[top-
1],i)+eps)top--;
stack[++top]=i;
}
stack[++top]=
0;
rep(i,mid+
1,r){
while(j<top&&getk(
stack[j],
stack[j+
1])+eps>p[i].k)j++;
f[p[i].id]=max(f[p[i].id],p[
stack[j]].x*p[i].a+p[
stack[j]].y*p[i].b);
}
solve(mid+
1,r);
l1=l;l2=mid+
1;
rep(i,l,r)
if(((p[l1].x<p[l2].x||(
fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y))||l2>r)&&l1<=mid)t[i]=p[l1++];
else t[i]=p[l2++];
rep(i,l,r)p[i]=t[i];
}
int main()
{
scanf(
"%d%lf",&n,&f[
0]);
rep(i,
1,n){
scanf(
"%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
p[i].k=-p[i].a/p[i].b;p[i].id=i;
}
sort(p+
1,p+
1+n);
solve(
1,n);
printf(
"%.3lf\n",f[n]);
return 0;
}
