摘要：
门户网站的主题是：不想写……扔掉链接就跑。我先回来，发现每一笔交易都必须是全额交易，因为你的交易表明它是有利可图的，因为两个交易量之间的汇率差异在一天后就很明显了。那么你必须得到充分的兴趣。这肯定比许多天的结合要好$f[i]$表示您在$i$日可以获得的最大金额可以更改为当天$A$卷的数量。枚举要使用的当天剩余的卷，根据当天的汇率更新最大金额，然后使用此金额更新$f[i]$。这是$O（n^2）$#include＜iostream＞#i
题意：不想写...
好吧我回来了
首先发现每次兑换一定是全部兑换，因为你兑换说明有利可图，是为了后面的某一天两种卷的汇率差别明显而兑换
那么一定拿全利啊，一定比多天的组合好
$f[i]$表示第$i$天最多能得到的钱在这一天可以换成多少$A$卷
枚举使用哪一天留下的卷，按这一天的汇率换成钱来更新最大钱数
再用这个钱数更新$f[i]$
这样是$O(n^2)$的
![BZOJ 1492: [NOI2007]货币兑换Cash [CDQ分治 斜率优化DP]第1张](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![BZOJ 1492: [NOI2007]货币兑换Cash [CDQ分治 斜率优化DP]第2张](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef long long ll; const int N=1e5+5,M=1e4+5; const double eps=1e-9; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,s; double a[N],b[N],r[N]; double f[N]; void dp(){ f[1]=s*r[1]/(a[1]*r[1]+b[1]); double t=s; for(int i=2;i<=n;i++){ for(int j=1;j<i;j++) t=max(t,f[j]*a[i]+f[j]/r[j]*b[i]); f[i]=max(f[i],t*r[i]/(a[i]*r[i]+b[i])); } printf("%.3lf",t); } int main(){ freopen("in","r",stdin); n=read();s=read(); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&r[i]); dp(); }
然后发现这个式子可以斜率优化
假设转移$j$比$k$更优，且$f_j<f_k$
令$g_i=frac{f_i}{r_i}$
$frac{g_k-g_j}{f_k-f_j} < -frac{a_i}{b_i}$
然后$f$不单调，所以用平衡树或者CDQ分治来维护
$CDQ$分治里左面按$x$排序，右面按$k$排序
注意：
CDQ分治中$l$和$1$一定别打错.........我$Debug$了好长时间
比较斜率的时候要$+eps$，精度太玄学了呜呜呜
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=1e5+5; const double eps=1e-9; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n; double d[N]; struct Day{ double a,b,r,k,x,y; int id; bool operator <(const Day &r)const{return k>r.k;} }p[N],t[N]; inline bool cmp(Day &a,Day &b){//a<b return a.x<b.x||(abs(a.x-b.x)<eps&&a.y<b.y); } inline double slope(int a,int b){ if(abs(p[a].x-p[b].x)<eps) return 1e20; else return (p[a].y-p[b].y)/(p[a].x-p[b].x); } int st[N],top; void Solve(int l,int r){//printf("Solve %d %d ",l,r); if(l==r){ d[l]=max(d[l],d[l-1]); p[l].y=d[l]/(p[l].a*p[l].r+p[l].b); p[l].x=p[l].y*p[l].r; return; } int mid=(l+r)>>1,p1=l,p2=mid+1; for(int i=l;i<=r;i++){ if(p[i].id<=mid) t[p1++]=p[i]; else t[p2++]=p[i]; } for(int i=l;i<=r;i++) p[i]=t[i]; Solve(l,mid); top=0; for(int i=l;i<=mid;i++){ while(top>1&&slope(st[top-1],st[top])<slope(st[top-1],i)+eps) top--; st[++top]=i;//printf("st %d ",i); } // int j=1; for(int i=mid+1;i<=r;i++){ while(j<top&&slope(st[j],st[j+1])+eps>p[i].k) j++; d[p[i].id]=max(d[p[i].id],p[st[j]].x*p[i].a+p[st[j]].y*p[i].b); } Solve(mid+1,r); p1=l;p2=mid+1; for(int i=l;i<=r;i++){ if(p1<=mid&&( p2>r||cmp(p[p1],p[p2]) )) t[i]=p[p1++]; else t[i]=p[p2++]; } for(int i=l;i<=r;i++) p[i]=t[i]; } int main(){ //freopen("in","r",stdin); freopen("cash.in","r",stdin); freopen("cash.out","w",stdout); n=read();d[0]=read(); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r), p[i].k=-p[i].a/p[i].b,p[i].id=i; sort(p+1,p+1+n); Solve(1,n); //for(int i=1;i<=n;i++) printf("hi %d %d %lf ",i,p[i].id,d[i]); printf("%.3lf",d[n]); return 0; }