首页 > 代码库 > 【BZOJ】1492: [NOI2007]货币兑换Cash（cdq分治）
【BZOJ】1492: [NOI2007]货币兑换Cash（cdq分治）
http://www.lydsy.com/JudgeOnline/problem.php?id=1492
蒟蒻来学学cdq神算法啊。。
详见论文 陈丹琦《从《Cash》谈一类分治算法的应用》
orz
此题表示被坑精度。。。。。导致没1a。。。开小号交了几发。。。。。。。。。。。。。。。。。。。。坑。
蒟蒻就说说自己的理解吧。。
首先这题神dp。。。（表示完全看不出来）
首先我们要最大化钱，那么可以将问题转化为最大化A券！（或B券）！！！！这点太神了，一定要记住这些！！
设d[i]表示前i天能得到的rmb全部买完A券和B券（如果剩余A和B券先卖掉再买，我也不知道为什么QAQ，然后百度了下，似乎是说，首先最大化了钱（即全部转化成了钱），然后再买入a券和b券。。为嘛。。），有
d[1]=S*rate[1]/(a[1]*rate[1]+b[1])，为什么呢，，你解下方程A*a[1]+B*b[1]=S, A/B=rate[1]....
d[i]=max{d[j]*a[i]+d[j]/rate[j]*b[i]}*rate[i]/(a[i]*rate[i]+b[i])，前边那个max是此时能得到的最多rmb，即从j天开始一直不动留到第i天。
然后显然这是$O(n^2)$的。。。
我们假设一下决策单调性（现在的dp都已经推广到任意假设然后任意维护了囧。。。。太神了orz。。看来1d1d应该完全可以优化到$O(nlogn)$及以下啊）
假设决策j和k，有$d[j]<d[k]$且决策j优于k，你看，全是假设！（下放的rate均写为r）
然后有：
$$d[j] \times a[i]+d[j]/r[j] \times b[i]>d[k] \times a[i]+d[k]/r[k] \times b[i]$$
稍稍化简可得到
$$(d[j]/r[j]-d[k]/r[k])/(d[j]-d[k])<-a[i]/b[i]$$
设$g[i]=d[i]/r[i]$，那么得到：
$$(g[j]-g[k])/(d[j]-d[k])<-a[i]/b[i]$$
那么可以得到，当
$$(g[j]-g[k])/(d[j]-d[k])<-a[i]/b[i] 且 d[j]<d[k]$$
时，决策j优于决策k
有什么好处呢？显然我们按建一颗维护凸线的（关键字为$d[i]$）的平衡树，然后二分找最优值。可是平衡树你愿意打么。。。。
所以cdq神犇就引入了cdq分治，orz
我们将所有的点看做$(d[i], g[i])$，我们想啊，假设对于决策i~n，我前边所有的j都求出来了，我不就可以排序了$d[j]$后然后维护凸线在单调$i~n$的斜率然后就能$O(n)$更新值了。这个可以参考1d1d四边形优化的单调栈更新后续状态的那个论文。
所以我们定义操作$solve(l, r)$表示$l~mid$的d值已经更新出来了，然后用这些点排序后维护凸线然后更新$mid+1~n$这些值。
哇塞，好神奇的样子！如果能在$solve(l, r)$用$O(n)$的时间搞定，那么复杂度为$O(nlogn)$！
于是cdq神犇就是搞出来了orz
首先我们分析假设$l~mid$的值都更新出来了，维护一个什么样的凸线？如果按我上边的推导，那么答案是上凸壳。
为什么呢？因为对于决策i，j比k优了，此时左式小于右式，我们的目标是找到第一个大于右式的k来更新答案，所以我们维护一个斜率递增的凸壳。因此是上凸壳。而右式显然也要维护单增的，因为对于决策j和k，如果j比k优了，那么对于更大的斜率，也不会再用到k。
上凸壳总会了吧。。。
那么再来考虑cdq分治。
我们需要实现：
$O(n)$实现$l~mid$维护出$d[i]$单调
$O(n)$实现$mid+1~n$维护出$-a[i]/b[i]$单调
而因为是分治，对于第一种情况，我们应该很自然的想到归并排序，那么完成。
对于第二种情况，我们可以预处理$1~n$的所有$-a[i]/b[i]$，然后在分治时取出>mid的点即可。
然后完成～撒花
那么考虑怎么取答案呢？答案是维护一个最大rmb的数组f，f[i]表示前i天最多得到的钱，那么转移是之前说过的。。。。。。。
所以当分治得到$l==r$时，我们要考虑更新$f[l]$，并且更新关于$l$的所有信息，即$g[l]$啥的。
初始化$f[0]=S$，所以我们再$l==r$时不得不加入$f[l]=max(f[l-1], f[l])$...
另外还要注意维护凸线一定要注意插入坐标系顶点，即(0,0)
所以看代码。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const int N=100005;const double eps=1e-8;struct dat { double x, y, r, a, b, k; int id; }t[N], p[N];const bool cmp(const dat &a, const dat &b) { return a.k<b.k; }double f[N];int n, s[N];inline const double getk(const int &j, const int &k) { return (p[j].y-p[k].y)/(p[j].x-p[k].x); }inline void fix(const int &i, const int &j) { f[p[i].id]=max(f[p[i].id], p[j].x*p[i].a+p[j].y*p[i].b); }void cdq(int l, int r) { if(l==r) { f[l]=max(f[l], f[l-1]); p[l].x=f[l]*p[l].r/(p[l].a*p[l].r+p[l].b); p[l].y=p[l].x/p[l].r; return; } int mid=(l+r)>>1, l1=l, l2=mid+1; for1(i, l, r) if(p[i].id<=mid) t[l1++]=p[i]; else t[l2++]=p[i]; for1(i, l, r) p[i]=t[i]; cdq(l, mid); int top=0; s[++top]=0; for1(i, l, mid) { while(top>1 && getk(s[top], s[top-1])<getk(s[top-1], i)+eps) --top; //被这里的eps恶心到了。。 s[++top]=i; } for1(i, mid+1, r) { while(top>1 && getk(s[top], s[top-1])+eps<p[i].k) --top; fix(i, s[top]); } cdq(mid+1, r); l1=l, l2=mid+1; top=l; while(top<=r) if(l1<=mid && (l2>r || p[l1].x<p[l2].x)) t[top++]=p[l1++]; else t[top++]=p[l2++]; for1(i, l, r) p[i]=t[i];}int main() { read(n); read(f[0]); for1(i, 1, n) { scanf("%lf%lf%lf", &p[i].a, &p[i].b, &p[i].r); p[i].id=i; p[i].k=-p[i].a/p[i].b; } sort(p+1, p+1+n, cmp); cdq(1, n); printf("%.3f", f[n]); return 0;}
Description
Input
Output
Sample Input
1 1 1
1 2 2
2 2 3
Sample Output
HINT
测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 1 000；
对于100%的测试数据，满足N ≤ 100 000；
Source
【BZOJ】1492: [NOI2007]货币兑换Cash（cdq分治）