[NOI2007]货币兑换

题目

题目描述

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A 券和 B 券的价值分别为$A_K$和$B_K$（元/单位金券）。

为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。

比例交易法分为两个方面：

a) 卖出金券：顾客提供一个[0，100]内的实数 OP 作为卖出比例，其意义为：将 OP%的 A 券和 OP%的 B 券以当时的价值兑换为人民币；

b) 买入金券：顾客支付 IP 元人民币，交易所将会兑换给用户总价值为IP 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 K 天恰好为 $Rate_K$；

例如，假定接下来 3 天内的 $A_K$、$B_K$、$Rate_K$的变化分别为：

时间	$A_K$	$B_K$	$Rate_K$
第一天	1	1	1
第二天	1	2	2
第三天	2	2	3

假定在第一天时，用户手中有 100 元人民币但是没有任何金券。

用户可以执行以下的操作：

时间	用户操作	人民币(元)	A 券的数量	B 券的数量
开户	无	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 行三个实数 $A_K$、$B_K$、$Rate_K$，意义如题目中所述。

输出格式：

只有一个实数 MaxProfit，表示第 N 天的操作结束时能够获得的最大的金钱数目。答案保留 3 位小数。

输入输出样例

输入样例#1：

输出样例#1：

225.000

说明

| 时间 | 用户操作 | 人民币(元) | A 券的数量 | B 券的数量| | :-: | :-: | :-: | :-: | :-: | | 开户 | 无 | 100 | 0 | 0 | | 第一天 | 买入 100 元 | 0 | 50 | 50 | | 第二天 | 卖出 100% | 150 | 0 | 0 | | 第二天 | 买入 150 元 | 0 | 75 | 37.5 | | 第三天 | 卖出 100% | 225 | 0 | 0 |

开户无 100 0 0

第一天买入 100 元 0 50 50

第二天卖出 100% 150 0 0

第二天买入 150 元 0 75 37.5

第三天卖出 100% 225 0 0

本题没有部分分，你的程序的输出只有和标准答案相差不超过$0.001$时，才能获得该测试点的满分，否则不得分。

测试数据设计使得精度误差不会超过$10^-7$。

对于 40%的测试数据，满足 N ≤ 10；

对于 60%的测试数据，满足 N ≤ 1 000；

对于 100%的测试数据，满足 N ≤ 100 000；

对于 100%的测试数据，满足：

0 <$A_K$≤ 10；

0 <$B_K$≤ 10；

0 <$Rate_K$≤ 100

MaxProfit ≤$10^9$

输入文件可能很大，请采用快速的读入方式。

必然存在一种最优的买卖方案满足：

每次买进操作使用完所有的人民币；

每次卖出操作卖出所有的金券。

题解

这道题看起来很麻烦

但是

必然存在一种最优的买卖方案满足：

每次买进操作使用完所有的人民币；

每次卖出操作卖出所有的金券。

所以$n^2$的动态转移方程就有了 $f_i=max(f_{i-1},\frac {f_j}{(r_ja_j+b_j)}r_ia_i+\frac {f_j}{(r_ja_j+b_j)b_i})$

这样肯定会TLE，发现方程是维护一个凸包，所以想到斜率优化

而这个凸包加点不是依次的，听说这样不用$CDQ$分治就是用$Splay$维护？

然后一通瞎打就行了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
# define mid (l+r>>1)
using namespace std;
const int MAX=1e5+1;
const double fs=1e-8;
int n,s;
struct p{
	double a,b,r,k;
	int pos;
	bool operator< (const p &a)
	const{
		return k<a.k;
	}
}mo[MAX],c[MAX];
struct q{
	double x,y;
	bool operator< (const q &a)
	const{
		return x<a.x;
	}
}a[MAX],b[MAX];
int qu[MAX];
double f[MAX];
double look(int x,int y)
{
	if(fabs(a[x].x-a[y].x)>fs) return -(a[x].y-a[y].y)/(a[x].x-a[y].x);
	return -1e8;
}
void solve(int l,int r)
{
	if(l==r)
	{
		f[l]=max(f[l],f[l-1]);
		a[l].x=f[l]/(mo[l].a*mo[l].r+mo[l].b);
		a[l].y=f[l]/(mo[l].a*mo[l].r+mo[l].b)*mo[l].r;
		return;
	}
	int L1=l-1,L2=mid;
	for(int i=l;i<=r;++i)
	  if(mo[i].pos<=mid) c[++L1]=mo[i];
	  else c[++L2]=mo[i];
	for(int i=l;i<=r;++i)
	  mo[i]=c[i];
	solve(l,mid);
	int L=1,R=0;
	for(int i=l;i<=mid;++i)
	  {
	  	while(L<R&&look(qu[R],qu[R-1])>look(qu[R],i)) --R;
	  	qu[++R]=i;
	  }
	for(int i=mid+1;i<=r;++i)
	  {
	  	while(L<R&&look(qu[L],qu[L+1])<mo[i].k) ++L;
	  	f[mo[i].pos]=max(f[mo[i].pos],mo[i].a*a[qu[L]].y+mo[i].b*a[qu[L]].x);
	  }
	solve(mid+1,r);
	sort(a+l,a+r+1);
}
int main()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;++i)
	  scanf("%lf%lf%lf",&mo[i].a,&mo[i].b,&mo[i].r),mo[i].k=mo[i].b/mo[i].a,mo[i].pos=i;
	f[0]=s;
	sort(mo+1,mo+1+n);
	solve(1,n);
	printf("%.3lf",f[n]);
	return 0;
}

题目