从《Cash》谈一类分治算法的应用.docx

《从《Cash》谈一类分治算法的应用.docx》由会员分享，可在线阅读，更多相关《从《Cash》谈一类分治算法的应用.docx（5页珍藏版）》请在第一文库网上搜索。

1、从Cash谈一类分治算法的应用分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同.求出子问题的解，就可得到原问题的解.分治算法非常基础，但是分治的思想却非常重要，本文将从今年NOI的一道动态规划问题Cash开始谈如何利用分治思想来解决一类与维护决策有关的问题：例一.货币兑换（Cash）i问题描述小Y最近在一家金券交易所工作.该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和8纪念券（以下简称B券）每个持有金券的顾客都有一个自己的帐户.金券的数目可以是一个实数.每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以

2、兑换的人民币数目.我们记录第K天中A券和B券的价值分别为Ak和Bk （元/单位金券）为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法.比例交易法分为两个方面：A）卖出金券：顾客提供一个0, 100内的实数OP作为卖出比例，其意义为：将OP%的A券和OP%的B券以当时的价值兑换为人民币；B）买入金券：顾客支付IP元人民币，交易所将会兑换给用户总价值为IP的金券并且满足提供给顾客的A券和B券的比例在第K天恰好为Reiter例如，假定接下来3天内的4、反、的变化分别为:时间AkBkRv4tek第一天111第二天122第三天223假定在第一天时，用户手中有100元人民币但是没有任何金券

3、.用户可以执行以下的操作：1 NOI 2007,货币兑换时间用户操作人民币(元)A券的数量B券的数量开户无10000第一天买入100元05050第二天卖出50%752525第二天买入60元155540第三天卖出100%20500注意到，同一天内可以进行多次操作.小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经 知道了未来N天内的A券和B券的价值以及RGe.他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能够获得多少元钱.算法分析不难确立动态规划的方程：设/团表示第i天将所有的钱全部兑换成A, B券，最多可以得到多少A券.很容易可以得到一个。(层)的算法：* Rate

4、l / (Al * Rate + Bl)SFor z AnsThen Ans 0.不妨设/网，gj=f1j/Ratej,那么(g7-g因)/(/ -,fk)-ai/hi.这样我们就可以用平衡树以为关键字来维护一个凸线，平衡树维护一个点集(/1心/)，/是单调递增的，相邻两个点的斜率是单调递减的每次在平衡树中二分查找与-矶i /卅最接近的两点之间的斜率.这样动态规划的时间复杂度就降低为。(川Og2)，但是维护凸线的平衡树实在不容易在考场中写对,编程复杂度高，不易调试(我的Splay代码有6k多).这个问题看上去只能用高级数据结构来维护决策的单调性，事实上我们可以利用分治的思想来提出一个编程复杂度

5、比较低的方法：对于每一个3它的决策/的范围为17-1.我们定义一个Solve过程：S。/阳/表示对于的品正广,ffl /JM的决策/来更新i的值.这样我们的目标就是So/阳1,)：可以先So/阳后计算出/川那么1/2的每一个数一定是/2+1的每个i的决策，用1M2的决策来更新M2+1的力i值后Solve(n/2+. n),这恰好体现的是一种分治的思想：用1/2的决策来更新/2+1的咒i值：类似用平衡树的方法，我们可以对1R2的所有决策建立一个凸线，对R2+1的所有，按照/殖从大到小排序，凸线的斜率是单调的，-。山田4也是单调的，这样我们就可以通过一遍扫描来计算出对于每一个i在1山2里面最优的决

6、策j.现在面临的问题是如何对于一段区间/,打维护出它的凸线：由于/口值是临时计算出来的，我们只需要递归的时候利用归并排序将每一段按照/口值从小到大排序，凸线可以临时用一个栈0()计算得出.下面给一个分治算法的流程：由于文苗/。田是已知的，不像.打斗是临时计算得出的.因此可以利用归并排序预处理，计算每一段/,打按照文四/。切排序后的i.Procedure Solved, r)If/=rThen更新助s,利用已经计算好的/的最优决策上 计算/口值，ExitMid (I + r) 12Solvent, mid -1)对/,加d-1这一段扫描一遍计算出决策的凸线，由于疝d+1 .打这一段以/用的排序在

7、预处理已经完成，因此只需要扫描一遍更新1 . r|的最优决策.Solve(mid+1, r)利用/,加d-1已排好序的/值和加d+1,川已排好序的/值归并排序将/,川这一段按加值排序.End Procedure至此，问题已经基本解决.时间复杂度为T5) = 2T(M2) + O()，因此算法的时间复杂度为O(log2)，NOI2007的测试数据最慢的测试点0.25,是一个相当优秀的算法.我们比较一下分治算法和用平衡树维护决策的方法：时间复杂度均为。(m0g2)，空间复杂度平衡树为。()，分治为0(10g2)(预处理。田/如 需要。(m0g2)的空间).但是编程复杂度却差别非常大，分治算法实现起

8、来相当简单,对于考场来说无疑是一个非常好的方法.在编程复杂度非常高的情况下，动态规划维护决策与分治思想很好的结合起来从而降低了编程复杂度，无疑是“柳暗花明又一村”.这种分治思想主要体现在将不断变化的决策转化成一个不变的决策集合，将在线转化为离线.下面我们再来看一个例题：例二.Mokia Balkan Olympiad in Informatics, 2007问题描述有一个的棋盘，每个格子内有一个数，初始的时候全部为0.现在要求维护两种操作：1) Add：将格子a, y)内的数加上A.2) Query：询问矩阵(xo,yo,xi,yi)内所有格子的数的和.数据规模：操作 1)0 160000,操

9、作 2) 0 10000, 1W 2000000.算法分析这个问题是IOI 2000 Mobile的加强版：Mobile中 吨1000,就可以利用二树状数组在。(1。822)的时间复杂度内维护出操作1)和操作2).这个问题中W很大,开二维树状数组0(储)的空间显然吃不消，考虑使用动态空间的线段树，最多可能达到操作次数* (logzW)2个节点，也相当大了.考虑使用分治思想来解决问题:将操作1)和操作2)按顺序看成是一个个事件，假设共有Tot个事件，Tot 170000.类似例题一，我们定义So/ue(/, r)表示对于每一个操作的事件i,将/泊的Add操作的所有属于i的矩形范围内的数值累加进来

10、.目标是Solve, ).假设计算 Solved R),递归 Solve(L, Mid), SolveMid + 1, r)后,对 L . Mid的所有A血操作的数值累加到Mid + 1 . R的所有匹配的操作的矩形中.后面这个问题等价于：平面中有个点，q个矩形，每个点有一个权值，求每个矩形内的点的权值之和.这个问题只需要对所有的点以及矩形的左右边界进行排序，用一维树状数组或线段树在O(p+q)log2W)的时间复杂度即可维护得出.因此问题的总的时间复杂度为O(7?*log27?”*log2W),不会高于二维线段树的O(*log2Mlog2W)的时间复杂度.上述这个算法无论是编程复杂度还是空间复杂度都比使用二维线段树优秀，分治思想又一次得到了很好的应用.在这个问题中，利用分治思想我们将一个在线维护的问题转化成一个离线问题，将二维线段树解决的问题降维用一维线段树来解决，使得问题变得更加简单.【例题一】是一个数据结构维护动态规划决策的问题，【例题二】为一个数据结构维护数据信息的问题.我们巧妙地使用分治思想，将在线维护的问题转化为离线问题，将变化的数据转化为不变的数据，使得问题解决更加的简单.