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 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;

}