自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 21:55:43，当前版本为作者最后更新于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$ 离散化。

代码如下：

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