优秀网站下载/兰州seo整站优化服务商

loj2353. 「NOI2007」 货币兑换

链接

https://loj.ac/problem/2353

思路

题目不重要，重要的是最后一句话

提示
必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。

所以f[i]表示第i天最大收益
设第i天把m元换成券（A券rate[i]*x个，B券x个），则\(a[i]*rate[i]*x+b[i]*x=m\)
\(x=\frac{m}{a[i]*rate[i]+b[i]}\)就可以算出来A券和B券了
根据提示，就可以把一天的所有钱都换掉
设x[j]=f[j]换成A券个数，y[j]=f[j]换成B券的个数（他们只跟j有关）
\(f[i]=a[i]*x[j]+b[i]*y[j]\)
\(\frac{f[i]}{b[i]}=\frac{a[i]}{b[i]}*x[j]+y[j]\)
\(y[j]=-\frac{a[i]}{b[i]}*x[j]+\frac{f[i]}{b[i]}\)
cdq进行dp维护凸包

代码

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
const int N=2e5+7;
int n,stak[N];
struct node {double a,b,rate,k,x,y;int id;bool operator < (const node &b) const {return k>b.k;}
}p[N],t[N];
double f[N];
double get_k(int a,int b) {if(!b) return -1e20;if(fabs(p[a].x-p[b].x)<eps) return 1e20;return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
void cdq(int l,int r) {if(l==r) {f[l]=max(f[l],f[l-1]); p[l].x=p[l].rate*(f[l]/(p[l].a*p[l].rate+p[l].b));p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);return;}int mid=(l+r)>>1;int l1=l,l2=mid+1;for(int i=l;i<=r;++i) {//sort p according to id if(p[i].id<=mid) t[l1++]=p[i];else t[l2++]=p[i];}for(int i=l;i<=r;++i) p[i]=t[i];cdq(l,mid);//solve left halfint top=0;for(int i=l;i<=mid;++i) {while(top>1&&get_k(stak[top-1],stak[top])<get_k(stak[top-1],i)+eps) top--;stak[++top]=i;}//get the upper convex hullstak[++top]=0;int j=1;for(int i=mid+1;i<=r;++i) {while(j<top&&get_k(stak[j],stak[j+1])+eps>p[i].k) j++;f[p[i].id]=max(f[p[i].id],p[i].a*p[stak[j]].x+p[i].b*p[stak[j]].y);}//use left hull to update right anscdq(mid+1,r);//continuel1=l,l2=mid+1;for(int i=l;i<=r;++i) {//sort p according to xif(((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++];elset[i]=p[l2++];}for(int i=l;i<=r;++i) p[i]=t[i];
}
int main() {scanf("%d%lf",&n,&f[0]);for(int i=1;i<=n;++i) {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);    cdq(1,n);printf("%.3lf",f[n]);return 0;
}