从Cash谈一类分治算法的应用分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同求出子问题的解，就可得到原问题的解分治算法非常基础，但是分治的思想却非常重要，本文将从今年NOI的一道动态规划问题Cash开始谈如何利用分治思想来解决一类与维护决策有关的问题：例一货币兑换(Cash) NOI 2007，货币兑换问题描述小Y最近在一家金券交易所工作该金券交易所只发行交易两种金券：A纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）每个持有金券的顾客都有 一个自己的帐户金券的数目可以是一个实数每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券 当天可以兑换的人民币数目我们记录第 K 天中 A 券和 B 券的价值分别为 AK 和 BK（元/单位金券）为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法 比例交易法分为两个方面：A)卖出金券：顾客提供一个0，100内的实数 OP 作为卖出比例，其意 义为：将 OP%的 A 券和 OP%的 B 券以
