题解 P4027 【[NOI2007]货币兑换】
panyf
2020-09-22 17:42:45
李超线段树解法，代码短，常数小，不卡精度！
先说 dp 方程。
注意到一个关键性质：每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。
设 $f_i$ 为第 $i$ 天最多拥有的钱数，$x_i$ 为第 $i$ 天用 $f_i$ 元钱可以兑换的 A 券数，$y_i$ 为 B 券数。
则有 $x_i=\dfrac{f_iRate_i}{a_iRate_i+b_i}$，$y_i=\dfrac{f_i}{a_iRate_i+b_i}$。
第 $i$ 天不卖出金券，则 $f_i=\max(f_i,f_{i-1})$。
第 $i$ 天卖出金券，枚举上一次买入的时间，可得 $f_i=\max a_ix_j+b_iy_j$。
变形得 $f_i=\max b_i(x_j\dfrac{a_i}{b_i}+y_j)$。
设 $k=x_j$，$x=\dfrac{a_i}{b_i}$，$b=y_j$，则 $f_i=\max b_i(kx+b)$，李超线段树优化即可。
注意到 $x$ 可能为小数，可以动态开点，精度和常数都较差。
对于此题，更好的方法是将所有的 $x$ 离散化。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
#define db double
db x[N],y[N],a[N],b[N],r[N],c[N],d[N];
int u,s[N*4];
#define f(i,t) (y[t]+x[t]*c[i])
void upd(int k,int t,int l,int r){
if(l==r){if(f(l,t)>f(l,s[k]))s[k]=t;return;}
int m=l+r>>1;
if(f(m,t)>f(m,s[k]))swap(t,s[k]);
f(l,t)>f(l,s[k])?upd(k*2,t,l,m):upd(k*2+1,t,m+1,r);
}//李超树插入
db qry(int k,int l,int r){
if(l==r)return f(u,s[k]);
int m=l+r>>1;
return max(f(u,s[k]),u>m?qry(k*2+1,m+1,r):qry(k*2,l,m));
}//李超树查询
int main(){
int n,i;
db f,g;
scanf("%d%lf",&n,&f);
for(i=1;i<=n;++i)scanf("%lf%lf%lf",a+i,b+i,r+i),c[i]=a[i]/b[i],d[i]=c[i];
sort(c+1,c+n+1);//离散化
for(i=1;i<=n;++i){
u=lower_bound(c+1,c+n+1,d[i])-c,f=max(f,b[i]*qry(1,1,n));
g=a[i]*r[i]+b[i],x[i]=f*r[i]/g,y[i]=f/g,upd(1,i,1,n);
}
printf("%.3lf",f);
return 0;
}
```