BZOJ 1492 [NOI2007 D1T2] 貨幣兌換Cash

2019-11-06 08:20:51

字體：大中小

供稿：網(wǎng)友

Description

小Y最近在一家金券交易所工作。該金券交易所只發(fā)行交易兩種金券：A紀(jì)念券（以下簡(jiǎn)稱A券）和 B紀(jì)念券（以下簡(jiǎn)稱B券）。每個(gè)持有金券的顧客都有一個(gè)自己的帳戶。金券的數(shù)目可以是一個(gè)實(shí)數(shù)。每天隨著市場(chǎng)的起伏波動(dòng)，兩種金券都有自己當(dāng)時(shí)的價(jià)值，即每一單位金券當(dāng)天可以兌換的人民幣數(shù)目。我們記錄第 K 天中 A券和 B券的價(jià)值分別為 AK 和 BK（元/單位金券）。為了方便顧客，金券交易所提供了一種非常方便的交易方式：比例交易法。比例交易法分為兩個(gè)方面：（a）賣(mài)出金券：顧客提供一個(gè) [0,100] 內(nèi)的實(shí)數(shù) OP 作為賣(mài)出比例，其意義為：將 OP% 的 A券和 OP% 的 B券以當(dāng)時(shí)的價(jià)值兌換為人民幣；（b）買(mǎi)入金券：顧客支付 IP 元人民幣，交易所將會(huì)兌換給用戶總價(jià)值為 IP 的金券，并且，滿足提供給顧客的A券和B券的比例在第 K 天恰好為 RateK；例如，假定接下來(lái) 3 天內(nèi)的 Ak、Bk、RateK 的變化分別為：

假定在第一天時(shí)，用戶手中有 100元人民幣但是沒(méi)有任何金券。用戶可以執(zhí)行以下的操作：

注意到，同一天內(nèi)可以進(jìn)行多次操作。小Y是一個(gè)很有經(jīng)濟(jì)頭腦的員工，通過(guò)較長(zhǎng)時(shí)間的運(yùn)作和行情測(cè)算，他已經(jīng)知道了未來(lái)N天內(nèi)的A券和B券的價(jià)值以及Rate。他還希望能夠計(jì)算出來(lái)，如果開(kāi)始時(shí)擁有S元錢(qián)，那么N天后最多能夠獲得多少元錢(qián)。

Input

輸入第一行兩個(gè)正整數(shù)N、S，分別表示小Y能預(yù)知的天數(shù)以及初始時(shí)擁有的錢(qián)數(shù)。接下來(lái)N行，第K行三個(gè)實(shí)數(shù)AK、BK、RateK，意義如題目中所述。對(duì)于100%的測(cè)試數(shù)據(jù)，滿足：0<AK≤10；0<BK≤10；0<RateK≤100；MaxPRofit≤10^9。【提示】1.輸入文件可能很大，請(qǐng)采用快速的讀入方式。2.必然存在一種最優(yōu)的買(mǎi)賣(mài)方案滿足：每次買(mǎi)進(jìn)操作使用完所有的人民幣；每次賣(mài)出操作賣(mài)出所有的金券。

Output

只有一個(gè)實(shí)數(shù)MaxProfit，表示第N天的操作結(jié)束時(shí)能夠獲得的最大的金錢(qián)數(shù)目。答案保留3位小數(shù)。

Sample Input

3 1001 1 11 2 22 2 3

Sample Output

225.000

HINT

Source

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

DP/CDQ分治+斜率優(yōu)化+DP~

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

#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分治+斜率優(yōu)化+DP。
“我們來(lái)分析對(duì)于i的兩個(gè)決策j和k，決策j比決策k優(yōu)當(dāng)且僅當(dāng)：
　(f [j] – f[k]) * A[i] + (f [j]/ Rate[j] – f [k] / Rate[k]) * B[i] > 0．
   不妨設(shè)f [j] < f [k]，g[j] = f [j]/ Rate[j]，那么
   (g[j] – g[k]) / (f[j] – f[k])< -a[i] / b[i]．”（摘自CDQ大神的論文~）
所以我們就先把每個(gè)時(shí)間看成一個(gè)點(diǎn)，按照k=-a/b從大到小排序分治。每次分治的時(shí)候分為左右兩個(gè)塊，按照id值歸到左右塊后向下分治左塊得出左面的結(jié)果，再用左塊的結(jié)果更新右塊的結(jié)果，最后向下分治右塊即可。
（函數(shù)里面記得要寫(xiě)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;}