题解 P4027 【[NOI2007]货币兑换】

李超线段树解法，代码短，常数小，不卡精度！

先说 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 离散化。

代码如下：

#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;
}