现在的位置: 首页 > 综合 > 正文

BZOJ 1492 NOI 2007 货币兑换Cash CDQ分治+斜率优化DP

2018年01月19日 ⁄ 综合 ⁄ 共 2475字 ⁄ 字号 评论关闭

题目大意:有两种金券,A和B。每一天有一个rate值,表示购入的比例;还有每一天AB金券的售价。现在给出初始的钱数,问最后能够获得多少钱。

思路:这算是神题了吧,啃论文啃别人代码将近一天才算有点明白。

首先题目中说的可以买一部分或者卖一部分是扯淡的,因为为了最大获利一定要全部买入,全部卖出。朴素的DP方程就好弄了。

设f[i]为第i天最多的B券的数量。那么f[i] = (rate[j] * f[j] * a[i] + f[j] * b[i]) / (rate[i] * a[i] + b[i])

整理一下,并设出x[j] = rate[j] * f[j] / (rate[i] * a[i] + b[i])

      y[j] = f[j] / (rate[i] * a[i] + b[i])

那么f[i] = a[i] * x[i] + b[i] * y[i]

这样就可以套用斜率优化来解决了。但是xy都是不单调的,所以不能用单调队列来维护,需要用Splay维护一个凸壳。想想昨天做的动态维护凸包,用set弄的都恶心了半天,这直接上Splay维护凸壳还是算了,乖乖啃论文上CDQ吧。。

第一次作CDQ的题,就被神犇引导到了这个题上。。总之还是大概总结了一下,CDQ分治基本的步骤。

1.当递归到底时,直接处理答案,然后返回。

2.弄出一个mid

3.递归解决[l,mid]

4.处理[l,mid]对[mid + 1,r]的影响(重要

5.递归解决[mid + 1,r]

6.将[l,mid]和[mid + 1,r]进行归并排序,为下一次处理区间之间的影响做准备。

此外CDQ分治的基础时间复杂度为O(nlogn),一般中间再套什么就乘上什么。一般来说树状数组比较常用,也就是O(nlog^2n)。

很可能用CDQ分治就避免了树套树等复杂的数据结构,保证了考场上时间充裕。(CDQ分治套树套树(O(nlog^3n)))

对于本题来说,我们需要在CDQ分治中处理凸壳上的点。每次处理左区间对右区间的影响的时候,先要按照询问的时间简单把左右区间分开,至少保证不会有Tj>Ti,j更新了i的情况。然后左边更新右边的情况就是完全合法的了。

分开之后,两侧的询问还是按照斜率排序的,所以用栈来维护左边形成的凸包,再用这个凸包来更新右边的点的f值,这些都是O(n)的。

最后归并起来,还是O(n)。总的时间复杂度就是O(nlogn),非常好的时间复杂度和代码复杂度。


CODE(没写Splay维护凸壳,不敢写。。。)

(若本蒟蒻的代码和hzwer犇的代码长得有几分相似,请不要见怪,因为我就是照他扒的。。。):


#include <cstdio>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
using namespace std;
#define max(a,b) ((a) > (b) ? (a):(b))

struct Ask{
	double a,b,rate,k;
	int pos;
	double x,y;
	
	bool operator <(const Ask &a)const {
		return k > a.k;
	}
	void Read(int p) {
		scanf("%lf%lf%lf",&a,&b,&rate);
		k = -a / b;
		pos = p;
	}
}ask[MAX],t[MAX];

int cnt;
double f[MAX];

inline double GetSlope(Ask *a,Ask *b)
{
	if(b == &ask[0])	return -1e20;
	if(a->x == b->x)	return 1e20;
	return (a->y - b->y) / (a->x - b->x);
}

void CDQ(int l,int r)
{
	if(l == r) {
		f[l] = max(f[l],f[l - 1]);
		ask[l].y = f[l] / (ask[l].a * ask[l].rate + ask[l].b);
		ask[l].x = ask[l].rate * ask[l].y;
		return ;
	}
	int mid = (l + r) >> 1;
	int l1 = l,l2 = mid + 1;
	for(int i = l; i <= r; ++i)
		if(ask[i].pos <= mid)	t[l1++] = ask[i];
		else	t[l2++] = ask[i];
	for(int i = l; i <= r; ++i)
		ask[i] = t[i];
	CDQ(l,mid);
	static Ask *stack[MAX];
	int top = 0;
	for(int i = l; i <= mid; ++i) {
		while(top > 1 && GetSlope(stack[top - 1],stack[top]) <= GetSlope(stack[top - 1],&ask[i]))
			--top;
		stack[++top] = &ask[i];
	}
	stack[++top] = &ask[0];
	int now = 1;
	for(int i = mid + 1; i <= r; ++i) {
		while(now < top && GetSlope(stack[now],stack[now + 1]) >= ask[i].k)
			++now;
		f[ask[i].pos] = max(f[ask[i].pos],stack[now]->x * ask[i].a + stack[now]->y * ask[i].b);
	}
	CDQ(mid + 1,r);
	l1 = l,l2 = mid + 1;
	for(int i = l; i <= r; ++i)
		if(((ask[l1].x < ask[l2].x || (ask[l1].x == ask[l2].x && ask[l1].y < ask[l2].y)) || l2 > r) && l1 <= mid)
			t[i] = ask[l1++];
		else
			t[i] = ask[l2++];
	for(int i = l; i <= r; ++i)
		ask[i] = t[i];
}

int main()
{
	cin >> cnt >> f[0];
	for(int i = 1; i <= cnt; ++i)
		ask[i].Read(i);
	sort(ask + 1,ask + cnt + 1);
	CDQ(1,cnt);
	cout << fixed << setprecision(3) << f[cnt] << endl;
	return 0;
}

抱歉!评论已关闭.