[NOI2007]货币兑换

嘟嘟嘟


懒的写博客了，恰好发现自己的思路跟某一老哥极其像，所以各位还是看这篇博客吧


写的CDQ分治，感觉不是很懂，以后还得再复习一遍。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
inline ll read()
{
	ll ans = 0;
	char ch = getchar(), last = ' ';
	while(!isdigit(ch)) {last = ch; ch = getchar();}
	while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}
	if(last == '-') ans = -ans;
	return ans;
}
inline void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n;
db s, a[maxn], b[maxn], rat[maxn];
int q[maxn], qry[maxn];

inline bool cmp(int i, int j)
{
	return a[i] * b[j] < a[j] * b[i];
}

db dp[maxn], ans = 0;
struct Point
{
	db x, y;
		inline bool operator < (const Point& oth)const
	{
		return x < oth.x || (x == oth.x && y < oth.y);
	}
}p[maxn], que[maxn];

inline bool slope(Point k, Point j, Point i)
{
	return (j.x - i.x) * (k.y - i.y) - (j.y - i.y) * (k.x - i.x) <= 0;
}
inline db calc(Point j, int i)
{
	return j.x * a[i] + j.y * b[i];
}

inline void cdqSolve(int L, int R)
{
	if(L == R)
	{
		if(dp[L - 1] > dp[L]) dp[L] = dp[L - 1];
		p[L].y = dp[L] / (rat[L] * a[L] + b[L]);
		p[L].x = rat[L] * p[L].y;
		return;
	}
	int mid = (L + R) >> 1, id1 = L, id2 = mid + 1, l = 1, r = 0;
	for(int i = L; i <= R; ++i) q[qry[i] <= mid ? id1++ : id2++] = qry[i];
	for(int i = L; i <= R; ++i) qry[i] = q[i];
	cdqSolve(L, mid);
	for(int i = L; i <= mid; ++i)
	{
		while(r > 1 && slope(que[r - 1], que[r], p[i])) --r;
		que[++r] = p[i];
	}
	for(int i = mid + 1; i <= R; ++i)
	{
		int j = qry[i];
		while(l < r && calc(que[l], j) <= calc(que[l + 1], j)) ++l;
		dp[j] = max(dp[j], calc(que[l], j));
	}
	cdqSolve(mid + 1, R);
	if(L == 1 && R == n) return;
	l = id1 = L; id2 = mid + 1;
	while(l <= R)
	{
		if(id2 > R || (id1 <= mid && p[id1] < p[id2])) que[l++] = p[id1++];
		else que[l++] = p[id2++];
	}
	for(int i = L; i <= R; ++i) p[i] = que[i];
	return;
}

int main()
{
	n = read(); scanf("%lf", &s);
	for(int i = 1; i <= n; ++i) scanf("%lf%lf%lf", &a[i], &b[i], &rat[i]), qry[i] = i;
	sort(qry + 1, qry + n + 1, cmp);
	dp[0] = s;
	cdqSolve(1, n);
	printf("%.3lf
", dp[n]);
	return 0;
}