从《cash》谈一类分治算法的应用

《从《cash》谈一类分治算法的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2008年信息学国家集训队作业雅礼中学　陈丹琦从《Cash》谈一类分治算法的应用分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同．求出子问题的解，就可得到原问题的解．分治算法非常基础，但是分治的思想却非常重要，本文将从今年NOI的一道动态规划问题Cash开始谈如何利用分治思想来解决一类与维护决策有关的问题：例一．货币兑换(Cash)NOI2007，货币兑换问题描述小Y最近在一家金券交易所工作．该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和B纪念券（以下简称B券）．每个持有金券的顾客都有一个自己的帐户．金券的数目

2、可以是一个实数．每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目．我们记录第K天中A券和B券的价值分别为AK和BK（元/单位金券）．为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法．比例交易法分为两个方面：A)卖出金券：顾客提供一个[0，100]内的实数OP作为卖出比例，其意义为：将OP%的A券和OP%的B券以当时的价值兑换为人民币；B)买入金券：顾客支付IP元人民币，交易所将会兑换给用户总价值为IP的金券，并且，满足提供给顾客的A券和B券的比例在第K天恰好为RateK；例如，假定接下来3天内的Ak、Bk、RateK的变

3、化分别为：时间AkBkRAtek第一天111第二天122第三天223假定在第一天时，用户手中有100元人民币但是没有任何金券．用户可以执行以下的操作：loanapprovalandpostcreditapprovalofficer/atalllevelsinaccordancewithcreditapprovalrules,licensingandeventualexerciseofcreditdecisionpowerofpersonsorinstitutions.Reviewfindingsandreviewcomments,accordingtotheBank'scred

4、it2008年信息学国家集训队作业雅礼中学　陈丹琦时间用户操作人民币(元)A券的数量B券的数量开户无10000第一天买入100元05050第二天卖出50%752525第二天买入60元155540第三天卖出100%20500注意到，同一天内可以进行多次操作．小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来N天内的A券和B券的价值以及Rate．他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能够获得多少元钱．算法分析不难确立动态规划的方程：设f[i]表示第i天将所有的钱全部兑换成A,B券，最多可以得到多少A券．很容易可以得到一个O(n2)的算法

5、：f[1]←S*Rate[1]/(A[1]*Rate[1]+B[1])Ans←SFori←2tonForj←1toi-1x←f[j]*A[i]+f[j]/Rate[j]*B[i]Ifx>AnsThenAns←xEndForf[i]←Ans*Rate[i]/(A[i]*Rate[i]+B[i])EndForPrint(Ans)O(n2)的算法显然无法胜任题目的数据规模．我们来分析对于i的两个决策j和k，决策j比决策k优当且仅当：　(f[j]–f[k])*A[i]+(f[j]/Rate[j]–f[k]/Rate[k])*B[i]>0．不妨设f[j]

6、ate[j]，那么(g[j]–g[k])/(f[j]–f[k])<-a[i]/b[i]．这样我们就可以用平衡树以f[j]为关键字来维护一个凸线，loanapprovalandpostcreditapprovalofficer/atalllevelsinaccordancewithcreditapprovalrules,licensingandeventualexerciseofcreditdecisionpowerofpersonsorinstitutions.Reviewfindingsandreviewcomments,accordingtotheBank'scredit2

7、008年信息学国家集训队作业雅礼中学　陈丹琦平衡树维护一个点集(f[j],g[j])，f[j]是单调递增的，相邻两个点的斜率是单调递减的．每次在平衡树中二分查找与-a[i]/b[i]最接近的两点之间的斜率．这样动态规划的时间复杂度就降低为O(nlog2n)，但是维护凸线的平衡树实在不容易在考场中写对L，编程复杂度高，不易调试(我的Splay代码有6k多)．这个问题看上去只能用高级数据结构来维护决策的单调性，事实上我们可以利用分治的思想来提出一个编程复杂度比较低的方法：对于每一个i，它的决策j