BZOJ1492：[NOI2007]货币兑换
【问题描述】
小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的变化分别为：
| 第一天 | 1 | 1 | 1 |
| 第二天 | 1 | 2 | 2 |
| 第三天 | 2 | 2 | 3 |
假定在第一天时，用户手中有100元人民币但是没有任何金券。
用户可以执行以下的操作：
| 开户 | 无 | 100 | 0 | 0 |
| 第一天 | 买入100元 | 0 | 50 | 50 |
| 第二天 | 卖出50% | 75 | 25 | 25 |
| 第二天 | 买入60元 | 15 | 55 | 40 |
| 第三天 | 卖出100% | 205 | 0 | 0 |
注意到，同一天内可以进行多次操作。
小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能够获得多少元钱。
【输入格式】
第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、BK、RateK，意义如题目中所述。
【输出格式】
只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。
【输入样例】
3 100
1 1 1
1 2 2
2 2 3
【输出样例】
225.000
【样例说明】
| 开户 | 无 | 100 | 0 | 0 |
| 第一天 | 买入100元 | 0 | 50 | 50 |
| 第二天 | 卖出100% | 150 | 0 | 0 |
| 第二天 | 买入150元 | 0 | 75 | 37.5 |
| 第三天 | 卖出100% | 225 | 0 | 0 |
【数据规模和约定】
输入第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、BK、RateK，意义如题目中所述。对于100%的测试数据，满足：0＜AK≤10；0＜BK≤10；0＜RateK≤100；MaxProfit≤10^9。
【提示】
1.输入文件可能很大，请采用快速的读入方式。
2.必然存在一种最优的买卖方案满足：
每次买进操作使用完所有的人民币；
每次卖出操作卖出所有的金券。
【解题思路】
有点贪心的想法：一有亏损就不去碰，一有利益就去全占。这必然导致要不全部卖出，要不全部买入。
①CDQ分治+斜率优化DP
O(N^2)的DP很好想。F[n]表示到第n天，没有金券可以得到的最大价值。
X[n]表示第n天的钱买金券可以得到的A劵数目；
Y[n]表示第n天的钱买金券可以得到的B劵数目；
\(Y[n]=\frac{F[n]}{A[n]*R[n]+B[n]}\)
\(Y[n]=X[n]*R[n]\)
\(F[n]=Max(X[i]*A[n]+Y[i]*B[n],F[n-1])\)
假如X[j]＜X[k]，并且k比j优。那么
\(X[k]*A[n]+Y[k]*B[n]>X[j]*A[n]+Y[j]*B[n]\)
转化一下式子：
\(\frac{Y[k]-Y[j]}{X[k]-X[j]}>-\frac{A[n]}{B[n]}\)
\(slop(j,k)=\frac{Y[k]-Y[j]}{X[k]-X[j]}\)
如果k比j优，则slop(j,k)>-A[n]/B[n]
单调队列加入F[i]时，当slop(q[qe-1],q[qe])＜slop(q[qe],i)，那么q[qe]是没必要存的。
假如-A[n]/B[n]是从大到小的。
∵若slop(q[qe],i)>-A[n]/B[n]，则i比q[qe]优，剔除q[qe]。
若slop(q[qe],i)＜-A[n]/B[n]，则q[qe]比i优，但slop(q[qe-1],q[qe])＜-A[n]/B[n]，q[qe-1]比q[qe]优，剔除q[qe]。
但这不能直接用斜率优化。X[i]和-A[i]/B[i]不一定同时有序。
CDQ分治可以很好的解决这一问题。
CDQ(L,R)表示处理id为L到R的F[]。
先按-A[i]/B[i]从大到小排序。
CDQ(1,n)
1、处理id在L~Mid的F[i]，CDQ(L,Mid)
2、用id在LR的F[i]。
有可能对于F[i]，最优解在F[j]处取得（Mid+1≤i≤N，1≤j≤Mid）
（因为LR的-A[i]/B[i]是有序的，满足斜率优化的条件）
3、处理id在Mid+1~R的F[i]，CDQ(Mid+1,R)。
有可能对于F[i]，最优解在F[j]处取得（Mid+1≤i≤N，Mid+1≤j＜i）
4、对id在L~R，按X[i]从小到大排序（类似归并）。
【代码】
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=100010;
const double inf=1e20;
const double eps=1e-8;
double f[N];
struct data
{
double x,y,a,b,k,r;
int id;
} p[N],t[N];
int n,qe,q[N];
double slop(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));
}
bool cmp(data A,data B) { return (A.k>B.k); }
void CDQ(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].r+p[L].b);
p[L].x=p[L].y*p[L].r;
return;
}
int Mid=(L+R)>>1;
int l1=L,l2=Mid+1; int h=1;
for(int i=L;i<=R;i++)
if(p[i].id<=Mid) t[l1++]=p[i]; else t[l2++]=p[i];
for(int i=L;i<=R;i++) p[i]=t[i];
CDQ(L,Mid);
qe=0;
for(int i=L;i<=Mid;i++)
{
while(qe>1 && slop(q[qe-1],q[qe])<slop(q[qe],i)+eps) qe--;
q[++qe]=i;
}
q[++qe]=0;
for(int i=Mid+1;i<=R;i++)
{
while(h<qe && slop(q[h],q[h+1])+eps>p[i].k) h++;
f[p[i].id]=max(f[p[i].id],p[q[h]].x*p[i].a+p[q[h]].y*p[i].b);
}
CDQ(Mid+1,R);
l1=L; l2=Mid+1;
for(int i=L;i<=R;i++)
{
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++];
}
for(int i=L;i<=R;i++) p[i]=t[i];
}
int main()
{
freopen("cash.in","r",stdin);
freopen("cash.out","w",stdout);
scanf("%d%lf",&n,&f[0]);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r);
p[i].id=i; p[i].k=-p[i].a/p[i].b;
}
sort(p+1,p+1+n,cmp);
CDQ(1,n);
printf("%.3lf\n",f[n]);
return 0;
}
②splay动态维护凸包
\(F[n]=X[i]*A[n]+Y[i]*B[n]\)
转化一下式子：
\(Y[i]=-\frac{A[n]}{B[n]}X[i]+\frac{F[n]}{B[n]}\)
其实就是使一次函数的截距最大（B[N]为定值，不用理）。
\(\frac{F[n]}{B[n]}=Y[i]+\frac{A[n]}{B[n]}X[i]\)
相当于一条斜率为-A[n]/B[n]的直线从上往下扫，碰到的第一个点(Xj,Yj)就是最优解（j＜n）
只需要维护一个凸包就行了，最优解只可能在凸包上，凸包内的点不会影响答案。
记得特判……
【代码】
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const double inf=1e9;
const int N=100010;
int n,root;
double f[N],A[N],B[N],r[N],X[N],Y[N];
double lk[N],rk[N];
int fa[N],ch[N][2],D[N];
int son(int x) { return (ch[fa[x]][1]==x); }
void rotate(int x)
{
int y=fa[x],z=son(x);
fa[x]=fa[y];
if(fa[y]) ch[fa[y]][son(y)]=x;
if(ch[x][1-z]) fa[ch[x][1-z]]=y;
fa[y]=x; ch[y][z]=ch[x][1-z]; ch[x][1-z]=y;
}
void splay(int x,int y)
{
for(;fa[x]!=y;)
{
if(fa[fa[x]]!=y)
(son(x)==son(fa[x]))?rotate(fa[x]):rotate(x);
rotate(x);
}
if(!y) root=x;
}
double getk(int i,int j)
{
if(fabs(X[j]-X[i])<eps) return -inf;
return((Y[j]-Y[i])/(X[j]-X[i]));
}
int pre(int x)
{
int y=ch[x][0],z=x;
for(;y;) if(getk(y,x)<=lk[y]+eps) z=y,y=ch[y][1]; else y=ch[y][0];
return z;
}
int suc(int x)
{
int y=ch[x][1],z=x;
for(;y;) if(getk(x,y)+eps>=rk[y]) z=y,y=ch[y][0]; else y=ch[y][1];
return z;
}
void inse(int &v,int f,int id)
{
if(!v) { v=id; fa[v]=f; splay(v,0); return; }
if(X[id]<=X[v]+eps) inse(ch[v][0],v,id); else inse(ch[v][1],v,id);
}
int find(int v,double k)
{
if(!v) return 0;
if(lk[v]+eps>=k && k+eps>=rk[v]) return v;
if(k>lk[v]) return find(ch[v][0],k); else return find(ch[v][1],k);
}
void updata(int x)
{
splay(x,0);
if(ch[x][0])
{
int lef=pre(x); splay(lef,x); ch[lef][1]=0;
lk[x]=rk[lef]=getk(lef,x);
} else lk[x]=inf;
if(ch[x][1])
{
int rig=suc(x); splay(rig,x); ch[rig][0]=0;
lk[rig]=rk[x]=getk(x,rig);
} else rk[x]=-inf;
if(lk[x]<=rk[x]+eps)
{
root=ch[x][0]; ch[root][1]=ch[x][1];
fa[ch[x][1]]=root; fa[x]=0;
rk[root]=lk[ch[root][1]]=getk(root,ch[root][1]);
}
}
int main()
{
freopen("cash.in","r",stdin);
freopen("cash.out","w",stdout);
scanf("%d%lf",&n,&f[0]);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&A[i],&B[i],&r[i]);
root=0;
for(int i=1;i<=n;i++)
{
double yu=-A[i]/B[i];
int now=find(root,yu);
f[i]=max(f[i-1],X[now]*A[i]+Y[now]*B[i]);
Y[i]=f[i]/(r[i]*A[i]+B[i]);
X[i]=Y[i]*r[i];
inse(root,0,i);
updata(i);
}
printf("%.3lf\n",f[n]);
return 0;
}