BZOJ 1492 [NOI2007 D1T2] 貨幣兌換Cash

2019-11-06 08:20:51

字體：大中小

來源：轉載

供稿：網友

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≤10^9?！咎崾尽?.輸入文件可能很大，請采用快速的讀入方式。2.必然存在一種最優的買賣方案滿足：每次買進操作使用完所有的人民幣；每次賣出操作賣出所有的金券。

Output

只有一個實數MaxProfit，表示第N天的操作結束時能夠獲得的最大的金錢數目。答案保留3位小數。

Sample Input

3 1001 1 11 2 22 2 3

Sample Output

225.000

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP/CDQ分治+斜率優化+DP~

容易想到的方法是直接DP，設f[i]為第i天最多擁有的A券數，那么n^2可以DP更新答案，但是時間復雜度較高，只能拿部分分。

#include<cstdio>#include<cstring>#include<iostream>using namespace std;int n;double f[100005],rat[100005],a[100005],b[100005],ans;int main(){	scanf("%d%lf",&n,&ans);	for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&rat[i]);	f[1]=ans*rat[1]/(a[1]*rat[1]+b[1]);	for(int i=2;i<=n;i++)	{		for(int j=1;j<i;j++) ans=max(ans,f[j]*a[i]+f[j]*b[i]/rat[j]);		f[i]=ans*rat[i]/(a[i]*rat[i]+b[i]);	}	printf("%.3f/n",ans);	return 0;}
滿分做法是CDQ分治+斜率優化+DP。
“我們來分析對于i的兩個決策j和k，決策j比決策k優當且僅當：
　(f [j] – f[k]) * A[i] + (f [j]/ Rate[j] – f [k] / Rate[k]) * B[i] > 0．
   不妨設f [j] < f [k]，g[j] = f [j]/ Rate[j]，那么
   (g[j] – g[k]) / (f[j] – f[k])< -a[i] / b[i]．”（摘自CDQ大神的論文~）
所以我們就先把每個時間看成一個點，按照k=-a/b從大到小排序分治。每次分治的時候分為左右兩個塊，按照id值歸到左右塊后向下分治左塊得出左面的結果，再用左塊的結果更新右塊的結果，最后向下分治右塊即可。
（函數里面記得要寫return……）
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define eps 1e-9int n,q[100001];double f[100001];struct node{	double a,b,rate,k,x,y;	int id;}a[100001],c[100001];double fabs(double u){	return u>0 ? u:-u;}double che(int u,int v){	if(!v) return -1e20;	if(fabs(a[u].x-a[v].x)<eps) return 1e20;	return (a[v].y-a[u].y)/(a[v].x-a[u].x);}bool Operator < (node u,node v){	return u.k>v.k;}void findd(int l,int r){	if(l==r)	{		f[l]=max(f[l],f[l-1]);		a[l].y=f[l]/(a[l].a*a[l].rate+a[l].b);		a[l].x=a[l].y*a[l].rate;		return;	}	int mid=(l+r)>>1,l1=l,l2=mid+1,j=1,tot=0;	for(int i=l;i<=r;i++)	  if(a[i].id<=mid) c[l1++]=a[i];	  else c[l2++]=a[i];	memcpy(a+l,c+l,sizeof(a[0])*(r-l+1));	findd(l,mid);	for(int i=l;i<=mid;i++)	{		while(tot>1 && che(q[tot-1],q[tot])<che(q[tot-1],i)+eps) tot--;		q[++tot]=i;	}	q[++tot]=0;l1=l;l2=mid+1;	for(int i=mid+1;i<=r;i++)	{		while(j<tot && che(q[j],q[j+1])+eps>a[i].k) j++;		f[a[i].id]=max(f[a[i].id],a[i].a*a[q[j]].x+a[i].b*a[q[j]].y);	}	findd(mid+1,r);	for(int i=l;i<=r;i++)	  if((a[l1].x<a[l2].x || (fabs(a[l1].x-a[l2].x)<eps && a[l1].y<a[l2].y) || l2>r) && l1<=mid) c[i]=a[l1++];	  else c[i]=a[l2++];	memcpy(a+l,c+l,sizeof(a[0])*(r-l+1));}int main(){	scanf("%d%lf",&n,&f[0]);	for(int i=1;i<=n;i++)	{		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].rate);		a[i].k=-a[i].a/a[i].b;a[i].id=i;	}	sort(a+1,a+n+1);	findd(1,n);	printf("%.3lf/n",f[n]);	return 0;}