Bzoj1492 [noi2007]货币兑换cash

玄学CDQ分治

Posted by yjjr's blog on February 19, 2018

标签:CDQ分治,凸包,DP

题目

题目传送门

Description

小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 的变化分别为: 这里写图片描述 假定在第一天时,用户手中有 100元 人民币但是没有任何金券。

用户可以执行以下的操作: 这里写图片描述 注意到,同一天内可以进行多次操作。

小Y是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来N天内的A券和B券的价值以及Rate。

他还希望能够计算出来,如果开始时拥有S元钱,那么N天后最多能够获得多少元钱。

Input

输入第一行两个正整数N、S,分别表示小Y能预知的天数以及初始时拥有的钱数。

接下来N行,第K行三个实数AK、BK、RateK,意义如题目中所述。

对于100%的测试数据,满足:0<AK≤10;0<BK≤10;0<RateK≤100;MaxProfit≤1 0^9。

Output

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

Sample Input

3 100

1 1 1

1 2 2

2 2 3

Sample Output

225.000

HINT

这里写图片描述

  1. 输入文件可能很大,请采用快速的读入方式。
  2. 必然存在一种最优的买卖方案满足: 每次买进操作使用完所有的人民币; 每次卖出操作卖出所有的金券。

题意

有AB两种货币,每天可以可以付Pi元,买到A券和B券,且A:B=Ratei,也可以卖掉OPi%的A券和B券,每天AB价值为Ai和Bi。开始有S元,n天后手中不能有AB券,问最大获益。

分析

显示O(n^2)DP

设f[i]表示前i天的最大收益

第i天将手中的钱全部换掉,可以换成的A券数目X(i):

第i天将手中的钱全部换掉,可以换成的B券数目Y(i):

第i天将第j天的AB券全部卖掉:

则状态转移方程为

那么我们需要求

转化为直线方程

使这条直线的截距最大

设X(j) < X(k),当k比j更优时需要满足

因为X(i)可能不是单调的,所以不能够用单调队列来维护,我们这里需要维护一个凸壳

然后就用到了CDQ分治(第一次写,膜了黄学长代码qwq)

CDQ分治大题思想就是进行左区间的分治时考虑对右区间的影响

按照时间轴分治,把每天看成一个点,首先将所有点按照斜率排序

并且保证操作结束后按照x,y升序排列

具体步骤代码里有详细注释

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
#define eps 1e-6
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6;
int n,top,stack[maxn];double f[maxn];
struct point{double x,y,a,b,k,rate;int w,id;}p[maxn],t[maxn];
inline double getk(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);
}//用于维护凸壳 
inline bool operator < (point a,point b){return a.k>b.k;}
void solve(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].rate+p[l].b);
		p[l].x=p[l].rate*p[l].y;
		return;
	}//分治结束直接计算结果 
	int l1=l,mid=(l+r)>>1,l2=mid+1,j=1;
	rep(i,l,r)
		if(p[i].id<=mid)t[l1++]=p[i];else t[l2++]=p[i];
	rep(i,l,r)p[i]=t[i];//将原顺序分为左右两块 
	solve(l,mid);//递归处理左区间 
	top=0;
	rep(i,l,mid){
		while(top>1&&getk(stack[top-1],stack[top])<getk(stack[top-1],i)+eps)top--;
		stack[++top]=i;
	}//扫一遍求出左区间的下凸线 
	stack[++top]=0;
	rep(i,mid+1,r){
		while(j<top&&getk(stack[j],stack[j+1])+eps>p[i].k)j++;
		f[p[i].id]=max(f[p[i].id],p[stack[j]].x*p[i].a+p[stack[j]].y*p[i].b);
	}//计算左区间对右区间的影响,扫一遍更新右区间答案 
	solve(mid+1,r);//递归处理右区间 
	l1=l;l2=mid+1;
	rep(i,l,r)
	   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++];
    rep(i,l,r)p[i]=t[i];//将区间按照x,y升序排列 
} 
int main()
{
	scanf("%d%lf",&n,&f[0]);
	rep(i,1,n){
		scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
		p[i].k=-p[i].a/p[i].b;p[i].id=i;
	}
	sort(p+1,p+1+n);//按斜率进行排序 
	solve(1,n);
	printf("%.3lf\n",f[n]);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr