假定在第一天时，用户手中有 100元 人民币但是没有任何金券。用户可以执行以下的操作：
注意到，同一天内可以进行多次操作。小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能够获得多少元钱。只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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;}
新闻热点
疑难解答
