首页 > 其他 > 详细

BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)

时间:2018-12-12 23:22:05      阅读:224      评论:0      收藏:0      [点我收藏+]

BZOJ
洛谷

如果某天能够赚钱,那么一定会在这天把手上的金券全卖掉。同样如果某天要买,一定会把所有钱花光。

那么令\(f_i\)表示到第\(i\)天所拥有的最多钱数(此时手上没有任何金券),可以选择什么都不干,\(f_i=f_{i-1}\);也可以从之前的某一天\(j\)\(f_j\)的钱买金券,在第\(i\)天全卖掉。用第\(j\)天的信息算一下买了多少\(A,B\),就可以得到第\(i\)天卖了多少钱。

所以有\(f_i=\max\{f_{i-1},\ A_i\frac{f_jk_j}{A_jk_j+B_j}+B_i\frac{f_j}{A_jk_j+B_j}\}\)

把后面那部分写成直线的形式:\(\frac{f_i}{B_i}-\frac{A_i}{B_i}*\frac{f_jk_j}{A_jk_j+B_j}=\frac{f_j}{A_jk_j+B_j}\),令\(x_j=\frac{A_i}{B_i}*\frac{f_jk_j}{A_jk_j+B_j},\ y_j=\frac{A_i}{B_i}*\frac{f_j}{A_jk_j+B_j}\)\(\frac{f_i}{B_i}-\frac{A_i}{B_i}x_j=y_j\)。要求用\(k=-\frac{A_i}{B_i}\)的直线去切\((x_j,y_j)\)使得截距最大,也就是维护上凸壳。

\(x\)即每个决策点不是单调的,就需要平衡树/CDQ分治去维护凸包。

CDQ分治:

先将所有点按斜率\(k\)排序。

先处理完左区间询问,然后将左区间按横坐标\(x\)归并排好序。这样处理右区间询问的时候(现在只考虑当前左区间对整个右区间询问的影响,也就是要对左区间维护上凸壳),左区间的\(x\)有序就可以直接用单调栈把上凸壳维护出来了。

而右区间已经按斜率\(k\)排好序了,所以可以\(O(n)\)在上凸壳中得到最优解(实现当前整个左区间对右区间的转移)。

当递归到\(l=r\),就说明已经处理完该点\(l\)之前的点对\(l\)的影响了,就可以直接得到\(f_l\)的值(顺便要和\(f_{l-1}\)\(\max\))并更新\(l\)这个决策点的信息了。

平衡树:

节点按\(x\)排序。每个节点维护与左边点和右边点的斜率\(lk,rk\)。(树上的节点都是凸包上的,凸包内部的就不要了)

对于新的决策点\(x\),直接先插入到平衡树中。

然后将\(x\)转到根。先找左边第一个能与\(x\)构成凸包的点:若当前点\(y\)与前一个点的斜率\(lk\gt k(x,y)\),那么如果\(y\)右边还有在凸包上的点,就继续向右找(没有就结束)。否则若\(lk\lt k(x,y)\),则应继续往左找。

找右边第一个能与\(x\)构成凸包的点同理。

最后,如果\(x\)就在凸包里面,即\(lk(x)<rk(x)\),就要把\(x\)从平衡树中删掉。

查询就根据斜率直接查询最优决策点了。


CDQ分治:


Splay:(快好多啊)

BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)

原文:https://www.cnblogs.com/SovietPower/p/10111492.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!