[bzoj 1492] [NOI2007]货币兑换Cash

有A, B两种金券和人民币. 每天A, B券有价值a, b (元/单位金券) 和一个比例r. 支持两种操作, 每天操作种类和次数不限: - 卖出金券: 将o%的A券和o%的B券以当天的价值兑换为人民币. o是顾客提供的[0,100]内的实数. - 买入金券: 支付i元人民币, 兑换当天总价值为i的金券, 其中A, B之比为当天的参数r.

已知天数N, 初始钱数S, 未来N天每天的参数a, b和r, 求N天后最多能获得多少元人民币, 保留3位小数. (测试数据保证精度误差不会超过10^-7; N≤10^5, 0<a,b≤10, 0<r≤100, 答案≤10^9, a, b, r是实数)

题面上的提示: 采用快速的读入方式; 必然存在一种最优方案满足: 每次买进使用完所有人民币, 每次卖出所有金券. 一道很经典的题. 根据提示, 结合样例, 可知每天只有4种选择: - 什么也不干 / 钱->金券->钱 - 金券->钱 - 钱->金券 - 金券->钱->金券

第4种操作用于调整所持有的A, B券的比例. 其他操作序列总与上述四种之一等价.

设为第天能获得的最多钱数, 为第天能买得的最多A券, 为第天能买得的最多B券. 由于限定在第天卖出, 和的最优值总能同时取得 - 钱最多的时候. 枚举第天的钱是怎么得到的 (昨天的? 今天卖掉某天购得的金券? )

的递推式和平面上的线性规划具有相同的形式:

(我自己的递推式已经手动将代入似乎看不出什么......QAQ)

要求直线过某个且纵截距最大. 某条斜率确定的直线自y轴正无穷向负无穷移动, 碰到的第一个一定是这个点集上凸壳上的一点. 维护上凸壳即可. 也可以用代数的语言证明, 但直观性欠缺.

如果直线的斜率和新点的横/纵坐标同时具有单调性 (HNOI 玩具装箱), 可以用单调栈维护凸壳, 用一个指针在栈内扫最优点 (上凸壳相邻两点连线的斜率单调递减, 某直线的最优点满足: 直线的斜率夹在该点与左右相邻两点连线的斜率之间). 本题两者均不满足单调性, 所以: - 用平衡树 (Splay) 维护凸壳. - 或者用CDQ分治.

两种方法都写了一下.

写Splay的时候, 为了避免精度问题 (其实本题不必要) 写了个返回-1/0/1的三态函数比较浮点数的大小, 然而后来忘了大于返回的是-1不是0......

写CDQ分治的时候问题更多......排序前后的下标弄混; 事实上, 像论文中说的那样, 我用预处理了每层排序的结果, 但这部分写错了, 根本没排序......

CDQ分治将序列分成两段, 把贡献拆为三部分: 前面对前面, 后面对后面, 前面对后面. 三部分的顺序得注意, 比如本题要先更新前面对后面, 再更新后面对后面. 前两部分递归计算, 最后一部分, 对前面的建立凸壳 (水平序Graham算法), 后面的询问按-a/b从大到小排序, 这样就可以线性处理了. 对点集中的点排序可以边分治边归并; 对询问按-a/b排序可以先用归并排序预处理 (空间复杂度), 也可以先对整个序列sort一遍, 再进行归并排序的逆过程.

Splay

const int N = 1e5 + 1;
const double Zero = 0, inf = 1.0/Zero, eps = 1e-9;

inline int dcmp(double x, double y)
{
	double z = y-x;
	return fabs(z) < eps ? 0 : (z > 0 ? 1 : -1);
}

struct Point {
	double x, y;
	Point(double x=0, double y=0): x(x), y(y) {}
	bool operator<(const Point& o) const
	{
		int d = dcmp(x, o.x);
		return d == 1 || (!d && dcmp(y, o.y) == 1);
	}
	bool operator==(const Point& o) const
	{
		return !dcmp(x, o.x) && !dcmp(y, o.y);
	}
	Point operator-(const Point& o) const
	{
		return Point(x-o.x, y-o.y);
	}
	friend double cross(const Point& a, const Point& b)
	{
		return a.x * b.y - b.x * a.y;
	}
	friend double slope(const Point& a, const Point &b)
	{
		return (a.y - b.y) / (a.x - b.x);
	}
};

namespace Convex_Hull {
	struct Node {
		Point p;
		double k[2];
		int t;
		Node* fa, * ch[2];

		Node(double=0, double=0);
		void* operator new(size_t);
		void setf(Node*, int);
	} * root, nodes[N + 1], * nil = nodes;

	Node::Node(double x, double y): p(x, y), t(-1), fa(0)
	{
		ch[0] = ch[1] = nil;
		k[0] = inf;
		k[1] = -inf;
	}

	void* Node::operator new(size_t)
	{
		static Node* ptr = nodes + 1;
		return ptr++;
	}

	inline void Node::setf(Node* f, int t1)
	{
		t = t1;
		fa = f;
		t >= 0 ? f->ch[t] = this : root = this;
	}

	inline void rot(Node* y)
	{
		int t = y->t;
		Node* x = y->fa;
		y->setf(x->fa, x->t);
		y->ch[t^1]->setf(x, t);
		x->setf(y, t^1);
	}

	void splay(Node* x, Node* r=0)
	{
		Node* y;
		while ((y = x->fa) != r) {
			if (y->fa != r)
				rot(x->t ^ y->t ? x : y);
			rot(x);
		}
	}

	bool insert(Node* x)
	{
		if (!root) return root = x, false;
		Node* y = root;
		while (true) {
			if (x->p == y->p) return false;
			int d = y->p < x->p;
			if (y->ch[d] == nil) {
				x->setf(y, d);
				break;
			} else y = y->ch[d];
		}
		splay(x);
		return true;
	}

	Node* walk(Node* y, int d)
	{
		Node* x = y->ch[d];
		while (x->ch[d^1] != nil) x = x->ch[d^1];
		if (x != nil) splay(x, y);
		return x;
	}
	
	void process(Node* a, Node* b, int d)
	{
		int t, f = d ? 1 : -1;
		while (t = dcmp(a->k[d] = slope(a->p, b->p), b->k[d]), t == 0 || t == f) {
			Node* c = walk(b, d);
			c->setf(a, d);
			b = c;
		}
		b->k[d^1] = a->k[d];
	}

	void add(double x, double y)
	{
		Node* a = new Node(x, y);
		if (!insert(a)) return;
		Node* l = walk(a, 0), * r = walk(a, 1);
		if (l != nil && r != nil && cross(a->p - l->p, r->p - a->p) > -eps) {
			l->setf(0, -1);
			r->setf(l, 1);
			return;
		}
		if (l != nil) process(a, l, 0);
		if (r != nil) process(a, r, 1);
	}

	Point query(double k)
	{
		Node* x = root;
		while (true) {
			int d0 = dcmp(x->k[0], k), d1 = dcmp(k, x->k[1]);
			if (d0 <= 0 && d1 <= 0) return x->p; // x->k[0] >= k >= x->k[1]
			x = x->ch[d1 == 1];
		}
	}
}

using Convex_Hull::add;
using Convex_Hull::query;

int main()
{
	int n;
	double f;
	scanf("%d%lf", &n, &f);
	add(0, 0);
	For (i, 1, n) {
		double a, b, r;
		scanf("%lf%lf%lf", &a, &b, &r);
		Point p = query(-a/b);
		f = max(f, a*p.x + b*p.y);
		
		double t = a*r + b;
		add(f*r/t, f/t);
	}
	printf("%.3f\n", f);
	return 0;
}

CDQ分治

#define fst first
#define sec second

typedef pair<double, int> Pair;

const int N = 1e5, LG_N = 17;
const double eps = 1e-9;

inline double dcmp(double x, double y)
{
	double z = y-x;
	return fabs(z) < eps ? 0 : (z > 0 ? 1 : -1);
}

struct Point {
	double x, y;
	Point(double x=0, double y=0): x(x), y(y) {}
	Point operator-(const Point& o) const
	{
		return Point(x-o.x, y-o.y);
	}
	bool operator<(const Point& o) const
	{
		int dx = dcmp(x, o.x), dy = dcmp(y, o.y);
		return dx == 1 || (!dx && dy == 1);
	}
	friend double cross(const Point& a, const Point& b)
	{
		return a.x * b.y - a.y * b.x;
	}
} P[N + 1], S[N + 1];

Pair c[LG_N + 1][N + 1];

// [l, r)
void merge_sort(int k, int l, int r)
{
	if (r-l == 1) {
		c[k][l] = c[0][l];
		return;
	}
	int m = (l+r)/2;
	merge_sort(k+1, l, m);
	merge_sort(k+1, m, r);
	merge(c[k+1]+l, c[k+1]+m, c[k+1]+m, c[k+1]+r, c[k]+l);
}

double f[N + 1], a[N + 1], b[N + 1], r[N + 1];

void solve(int k, int l, int r)
{
	if (r-l == 1) {
		double t = a[l]*::r[l] + b[l];
		P[l] = Point(f[l]*::r[l]/t, f[l]/t);
		return;
	}
	int m = (l+r)/2, top = 0, p = 0;
	solve(k+1, l, m);
	Rep (i, l, m) {
		while (top > 1 && cross(S[top-1] - S[top-2], P[i] - S[top-1]) > -eps) --top;
		S[top++] = P[i];
	}
	Rep (i, m, r) {
		int now = c[k][i].sec;
		while (p < top-1 && cross(S[p+1] - S[p], Point(-b[now], a[now])) > eps) ++p;
		f[now] = max(f[now], a[now] * S[p].x + b[now] * S[p].y);
	}
	f[m] = max(f[m], f[m-1]);
	solve(k+1, m, r);
	inplace_merge(P+l, P+m, P+r);
}

int main()
{
	int n;
	scanf("%d%lf", &n, &f[1]);
	For (i, 1, n) {
		scanf("%lf%lf%lf", &a[i], &b[i], &r[i]);
		c[0][i] = Pair(a[i]/b[i], i);
	}
	merge_sort(0, 1, n+1);
	solve(1, 1, n+1);
	printf("%.3f\n", f[n]);
	return 0;
}