【斜率优化dp+cdq分治】货币兑换

分治, 动态规划DP

传送门：BZOJ1492

思路：用$f_i$表示第i天最多的钱数，并记录当天钱数能换的最大的A类钱以及对应的B类钱，发现可以斜率优化，但由于斜率似乎并不单调，要用cdq分治来保证斜率单调。

注意：算斜率横坐标相同时的特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 120000
int n,m,q[N];
double f[N];
struct node{
	int ID; double a,b,r,k,x,y;
	bool operator < (const node x) const {return k>x.k;}
}p[N],pp[N];
double K(int u,int v){if (fabs(p[u].x-p[v].x)<1e-10) return 1e20; return (p[u].y-p[v].y)/(p[u].x-p[v].x);}
void solve(int l,int r){
	if (l==r){
		f[l]=max(f[l],f[l-1]);
		p[l].x=f[l]/(p[l].a*p[l].r+p[l].b)*p[l].r; p[l].y=f[l]/(p[l].a*p[l].r+p[l].b);
		return;
	}
	int mid=(l+r)>>1;
	int j=l,k=mid+1;
	for (int i=l;i<=r;i++) if (p[i].ID<=mid) pp[j++]=p[i]; else pp[k++]=p[i];
	for (int i=l;i<=r;i++) p[i]=pp[i];
	solve(l,mid); int tt=1,ww=0;
	for (int i=l;i<=mid;i++){
		while (tt<ww && K(q[ww-1],q[ww])<=K(q[ww],i)) ww--;
		q[++ww]=i;
	}
	for (int i=mid+1;i<=r;i++){
		while (tt<ww && K(q[tt],q[tt+1])>=p[i].k) tt++;
		f[p[i].ID]=max(f[p[i].ID],p[q[tt]].x*p[i].a+p[q[tt]].y*p[i].b);
	}
	solve(mid+1,r); j=l,k=mid+1;
	for (int i=l;i<=r;i++){
		if ((j<=mid) && (p[j].x<p[k].x || (p[j].x==p[k].x && p[j].y<p[k].y) || k>r)) pp[i]=p[j++]; else pp[i]=p[k++];
	}
	for (int i=l;i<=r;i++) p[i]=pp[i];
}
int main(){
	scanf("%d%d",&n,&m); p[0].x=p[0].y=0; f[0]=m;
	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+n+1); solve(1,n);
	
	printf("%.3lf\n",f[n]);
	
	return 0;
}