loj2353. 「NOI2007」 货币兑换
链接
思路
题目不重要，重要的是最后一句话
提示
必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。
所以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 half
int 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 hull
stak[++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 ans
cdq(mid+1,r);//continue
l1=l,l2=mid+1;
for(int i=l;i<=r;++i) {//sort p according to x
if(((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++];
else
t[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;
}