一类单调问题的求解（课堂PPT）

1、1一类单调问题的求解中山纪念中学 宋新波2例0.老徐真人秀做到的？请老徐回答当时是怎么通过程序来快速选择。老徐是编程达人，决定天的最美味的苹果。只会吃天数不超过老徐有个怪癖，每一天干，供同一种美味的苹果若天，每一天节目组都提个真人秀，节目共录制最美杭城人老徐参加一1061NMMN随手扔过来下面这个：直接告诉你答案，当时老徐是大师，当然不会，老徐的做法如下：别为天提供的苹果美味度分，比如，79,73,78,75,80545MNday180day275day378day473day57980807875，既新鲜又美味，既新鲜又美味808079737978day5-day1=4天天793一.单调队列

2、及应用 。队列中的最大值在队首中维护单调减的队列，如例中是单调减的。素是单调的，如例由得队列中保留的元直接删除。没有存在的必要，可以比“既新鲜又美味”，跟，且，如果满足与中，区间中两个元素如例右移向右平移的。递增。查询区间是随着时，非递减，当左边界递增，的增加，右边界。随着，右边界中，区间左边界如例，天选择的苹果的美味度表示老徐第天发放苹果的美味度，表示第中，设如例0 0最最优优选选择择在在队队首首：保保持持队队列列单单调调：去去除除冗冗余余状状态态：区区间间出出现现平平移移：维维护护区区间间最最值值：五五大大要要点点：001, 1max01, 1maxmax0aaaaaaallrrlaajj

3、kjkkjiiiiijijkiMiiiMiijMiifiifi4一.单调队列及应用 结构。优于堆或线段树等数据时间复杂度为进出队列各一次，所以由于每个元素最多只会最优答案在队首插入元素删除队首元素删除队尾元素中的代码如下：例,;: ;: );();();()(1:; 0:; 1:0NOendstqaifiienqenincstincthenMstqiifendecdoenqaiaandstenwhilebegindontoiforenst代码实现：代码实现：5例1.NOIP2010初赛烽火传递。，的数据，对于的数据，对于一行，表示答案。代价。个烽火台发出信号所需，表示第行，每行一个数接下来个发

4、出信号。个烽火台中至少要有一表示在连续表示烽火台的个数，。其中第一行：两个整数。座城市之间准确出传递袭之时，情报能在这两少代价，才能使敌军来请计算总共最少花费多个发出信号。个烽火台中至少要有一连续使情报准确地传递，在号都有一定代价。为了发出信个烽火台，每个烽火台之间有递军情，在某两座城市晚燃烧干柴，以火光传通过浓烟表达信息；夜白天燃烧柴草，上。一旦有敌情发生，般建在险要或交通要道要的军事防御设施，一烽火台又称烽燧，是重100000100%100;1000%5026521435,WWiiNMNMiNMMNMNMN数据范围：数据范围：样例输出：样例输出：样例输入：样例输入：输出格式：输出格式：输入

5、格式：输入格式：题目描述：题目描述：6例1.NOIP2010初赛烽火传递 。间复杂度为使用单调队列优化，时在队首。持单调递增，最优决策，所以队列中的元素保删除，可以且，如果而且区间是向右平移的时要计算区间最小值，上式计算答案时时程：”得到以下状态转移方台的位置通过考虑“前一个烽火”所需最小代价。个烽火台一定发出信号个烽火台传递情报且第表示“在前动态规划：状态NOjfjkjfkfifNiMNifAnsMiijMijfMiifjiiifwwii1 ,1maxmin1min分析：分析：7例2.GDKOI2009猴子。，：吃到的香蕉数。个整数，为猴子最多能输出只有一行，包含一。总是位置。并且没有两棵树

6、在同一从近到远排列。输入保证这些树按照树到猴子所在树的距离上的香蕉数，以及这棵，分别表示每棵香蕉树个整数行每行包含两。下面最多跳跃次数距离，猴子每次跳跃的最大，分别是香蕉树的棵数输入第一行为三个整数多能吃多少个香蕉呢？香蕉都吃了。那么它最，它就会把那棵树上的。每当他跳到一棵树上得太远或跳的次数太多跳力也有限，它不能一次棵树上。同时猴子的体只想从一棵树跳到另一它又不想在地上走，而想吃尽量多的香蕉，但棵树上。这个猴子当然则在这排香蕉树的第一在同一直线上，而猴子蕉树，这些香蕉树都种一个猴子找到了很多香10000,5000%100;2000%50;100%3010976543806202550,0DN

7、MNMNMNMDNbabbaiiii数数据据范范围围：样样例例输输出出：样样例例输输入入：输输出出格格式式：输输入入格格式式：题题目目描描述述：8例2.GDKOI2009猴子。时间复杂度为最优值在队首。调递减的队列。移的，可以维护一个单的增加，区间是向下平值，同一列随着大列的连续元素的区间最时需要计算第，计算按照列从小到大来处理答案时且其中时：得到以下状态转移方程点考虑最后一次跳跃的起。棵树最多能吃多少香蕉次跳跃跳到第棵树不超过表示从第动态规划：状态NMOijjifMNfAnsjDikjkfijifkijjifbbaakii1, 11101,max0,1,0分分析析：ij-1j9例3.多重背包

8、且价值总和最大。不超过背包容量，使这些物品的体积总和。选择物品装入背包可价值是，件可用，体积是种物品最多有的背包。第种物品和一个容量为有wvmiiiiVN10例3.多重背包：分别用蓝色和红色标记要用到的元素示意图，和观察计算这里不做介绍当然用倍增法优化到时间复杂度为下状态转移方程：个物品装几个”得到以通过考虑“第值。个物品能获得的最大价的背包来装前表示用容量为背包问题，定义状态vmvmwviNiNiiiiiijifjifmVOVOjxxxjifijifiijjifi,*,*,min0*, 100,121log分析：分析：iji-1j-vij+vi11例3.多重背包NVOjjikkkjifkkk

9、jifkkkjifjifkjifjifjifjifjifjifjifvvvxxxwxvxvwxvxvxxxvxvxwxvxwxvxxxxxvviiiiiiiiiiiiiiiii时间复杂度为空间。的值分批次处理以节省按照模当然也可以把的状态等于模对应背包容量个单调队列，其中队列建立一行来做，每一行需要从小到大来处理，一行按可以永久删除。优，还是比的，跟上面的不等式是等价，而不等式对应着同样的可选决策对应着的可选决策来说于后面的某一个状态可以直接删除。因为对时，且满足：如果时，对于两个可选决策计算在向右平移；区间相对时涉及到的元素组成的计算等距的元素，距离为时涉及的元素是上一行置连续的元素，如计算

10、注意这里的区间不是位：活运用单调队列来优化由上图发现该题可以灵,00*, 1*, 1,*,*,*, 1*, 1,11211222211111221221程序实现：程序实现：去除冗余保持单调：去除冗余保持单调：区间出现平移：区间出现平移：维护区间最值：维护区间最值：分析：分析：12例4.HNOI2008Toy1072,1 ,50000141243145118ccLxcciijikkiLNNLNLPLxPijxjiPODZiNNPODZODZPP数据范围：数据范围：样例输出：样例输出：样例输入：样例输入：输出格式：输出格式：输入格式：输入格式：题目描述：题目描述：输出最小费用。行输入，接下来和第一

11、行输入两个整数，但他希望费用最小。甚至超过意长度的容器，他可以制造出任教授不关心容器的数目是一个常量。，其中，其制作费用为度为授的研究，如果容器长教器长度有关，根据。制作容器的费用与容，那容器的长度将为件玩具放在一个容器中到第如果将第形式地说，个单位长度的填充物。玩具之间要加入个玩具，那么相邻两件果一个一维容器中有多号是连续的。同时，如器中的玩具编教授要求在一个一维容。为了方便整理，处理后一维长度是件玩具经过件玩具，第的到号为教授有编一维容器中。维，再装到一种特殊的可以将任意物品变成一来给玩具装箱。自己的物体维度压缩器教授使用北京去。决定把所有玩具都运到堆智力玩具。于是，他他割舍不下自己的一大

12、教授要去看奥运，但是月13例4.HNOI2008Toy ，超时。直接做时间复杂度为入的分析。的单调性，需要深就可以删除”这样明显没有前面几个例子中“却没有分离，的，这两个参数是完全分离和这三项中式子中则有对应的费用记为。可选决策定义离注意展开过程中参数分，是未知的，展开平方式的含有这些量相当于已知，而时，计算其中下状态转移方程：这段连续的玩具，得以到设是装在同一个容器中，假考虑哪些玩具与玩具的前缀和。为用，个玩具装箱所需最小费表示把前动态规划：状态njififjjigjxigjxjxigififLjsisjicOjjjxigjijfjxigjfjfjjsjjxLisiigjsjjfjLisii

13、fijjfifijiisiifjji2112222222,*2,1*211,1,1,1,1,1min121分析：分析：14例4.HNOI2008Toy 斜率优化！题要用到新知识：两个点形成的斜率，这，上面式子左边像：是单调递增的，所以有因再令jjjjjjixjjjxjjxjigjjxjigjjxjigxxyyisiixifiyxxigffxigfxigf211212212212221212222*2)()()()(1,1*211-21*211*221的的前前提提条条件件：j jj j时时研研究究i if fi if fj jj j1 12 21 12 215例4.HNOI2008Toy 的结论

14、：增的。下面有两个重要都是单调的，都是单调和该题则必须满足优，令比，如果时，可选决策计算igixigTxxyyTifjjjjjjjjjjjj*2,)()()()(,211212211212斜斜率率优优化化： 再继续维护！列基础上加入新的决策时可以在之前维护的队并且在是最优的！优。所以队首比优，比优，比来说，则对于所以可以删除。优，永远比时，有：，计算后面的是单调增的，则对于由于之间的斜率策如果队列中相邻两个决。，, 11.,*2,.,*2,*2,*2*2,*2,*2,.,*2,*2,*2,.,11322113221111111322121iififigTigTigTxxygigyxTfiigi

15、gyxTyxigTigTigTigifjjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkk证明：证明：最优决策是队首元素最优决策是队首元素即：即：的斜率都要大于的斜率都要大于使得这些相邻决策之间使得这些相邻决策之间决策决策依次存储有价值的可选依次存储有价值的可选大大策，使得队列中从小到策，使得队列中从小到可以删除其中的冗余决可以删除其中的冗余决 到i,到i,时，所有可选决策是1时，所有可选决策是1结论1：计算结论1：计算16例4.HNOI2008Toyj1j2j3 可以删除。得证！不可能成为最优决策，出现了矛盾！所以优比优比。的过程中成为最优决策有没有可能在计算，分析即。邻斜率

16、单调递减的情况，假设出现下图所示相设队列中三个相邻决策jjjjjjjjjjjjjjjjjjjjjTigTigTigTfTT221323232211223221321,*2,*2,*2,证明：证明：决策之间的斜率单调增决策之间的斜率单调增结论2：可以维护相邻结论2：可以维护相邻 最最优优决决策策取取队队首首元元素素策策满满足足：应应该该维维护护队队列列中中相相邻邻决决综综上上：jjjjjjkkTTTig,.,*21322117例4.HNOI2008Toy ：最优决策在队首。；或者于直到队列中元素个数小，循环做下去，则删除队首元素，如果取队首两个决策加入队尾；：把新的可选决策或者列中的元素个数小于

17、。循环做下去，直到队则删除队尾元素如果策每次选队列最后两个决要插入新的可选决策取头取头删头：删头：插入插入删尾：删尾：igTigTiiTTiTTijjjjjjjjjjjjjjjjkkkkkkkkk*2,2*2,2,2112121111 步：下所以具体程序实现分以递增由于，坐标是插入点，相当于在二维平面中插入一个新的决策计算枚举维护相邻决策满足：的整个过程中，始终要在计算4,.,*213221ixiyixiiifiTTTigfjjjjjjkk程序实现：程序实现：18例4.HNOI2008Toy动画演示：动画演示：j1j2j3j4j5T(j3,j4)T(j4,j5)T(j2,j3)T(j3,j5)

18、T(j1,j2)2g(i)最优决策为最优决策为j219例4.HNOI2008Toy nOendistqtstqfifstincdoigstqstqtandenstwhileienqenincendecdoienqtenqenqtandenstwhilebegindontoiforenstf时间复杂度为取头删头插入去尾;);,(cos 1: );()*2)1,() 1( ;: );();(),),1() 1(1:; 0:; 1:; 0: 0程序代码：程序代码：20例5.APIO2010特别行动队的战斗力和更大。正后，没有其他方案能使修。修正后的战斗力和为为，修正后的战斗力分别战斗力分别为。特别行

19、动队的初始，第三队包含士兵，第二队包含士兵和士兵含士兵特别行动队：第一队包个士兵组成。此时，最佳方案是将。经验公式中的参数为名士兵，和。例如你有最大。试求出这个最大动队修正后战斗力之和编队，使得所有特别行你要为这支部队进行。作为部队统帅，现在是已知的系数其中式修正为将按如下经验公的初始战斗力总结出一支特别行动队。通过长期的观察，你之和，即为对内士兵初始战斗力战斗力一支特别行动队的初始的士兵的初始战斗力为编号为的序列。即为形如队员的编号应该连续，同一支特别行动队中战场。出于默契的考虑若干特别行动队调入编号，要将他们拆分成到队，士兵从名预备役士兵组成的部你有一支由94 , 1 , 44 , 3 ,

20、 44321320,10, 14, 3, 2, 24)0(,.,),.1,(1432121cbaacbacbxaxxxxikiiinnxxxxxxxxxkiiii题题目目描描述述：1001 ,000,000,10, 15,000,000, 11:%100;000,10:%50;1000:%20 xicbannn数据范围：数据范围：21例5.APIO2010特别行动队 分。可以得直接做，时间复杂度为其中。和这一项无法分离令尽量分离得：和未知。把已知，展开得其中则有：移，假设是的士兵”来进行状态转个士兵在同一个行动队通过考虑“跟第的前缀和。为战斗力修正战斗力。别行动队能获得的最大个士兵拆分成若干个

21、特表示把前动态规划：状态50,1,1*2max1*2*,1*1*1*21*11*1*2*1:1,1*1max,222222221111nisjsisjsjsisjsisxOijjsisaihjgifjijsisacisbaihjsbajfjgcisbajsisajsbajfjijicjsbisbajsisaajfijcjsisbajfifjiisiifi分分析析：22例5.APIO2010特别行动队 上一题用斜率优化！是单调的，可以考虑像的坐标是的坐标是中两个点形成的斜率，其，上面式子左边像上式得：是单调增的是正整数，因初始战斗力：时isgsgsisassggisssisaggsisaihgs

22、isaihgjjjjjjjjjjjjjjxxjjjjjjjjififjjijji22211121121211212112212,1,1*21111*21*21*212的前提条件的前提条件研究研究23例5.APIO2010特别行动队 个重要的结论：是单调增的，同样有两该题优，必须满足要比时换句话说，优，必须满足比。如果，令时，可选决策根据上面分析：计算isisaTisaTssggTifjjjjjjjjjjjjjjjjjj*2,*2,11,212121211212122112应应用用斜斜率率优优化化： 是最优的！优。所以队尾元素比，优，比优，比所以可以删除优，永远比时，有：，计算对于后面的是单调增

23、的，优。由于比之间的斜率策如果队列中相邻两个决。，jjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkkkkisaTisaTisaTyyxsaisayxTfiisyxisayxTyxisaTisaTisaTisaif1 -23121322111111322121.*2,.,*2,*2,*2*2,*2,*2,.,*2,*2,*2,.,证明：证明：最优决策是队尾元素最优决策是队尾元素即：即：大于大于相邻决策之间的斜率都相邻决策之间的斜率都依次存储可选决策依次存储可选决策，使得队列中从小到大，使得队列中从小到大时，可以删除冗余决策时，可以删除冗余决策结论1：计算结论1：计算24例5.A

24、PIO2010特别行动队 可以删除。得证！不可能成为最优决策，出现了矛盾！所以优比优比。的过程中成为最优决策有没有可能在计算，分析即。邻斜率单调递增的情况，假设出现下图所示相设队列中三个相邻决策jjjjjjjjjjjjjjjjjjjjjTisaTisaTisaTfTT232213232211223221321,*2,*2,*2,证明：证明：决策之间的斜率单调减决策之间的斜率单调减结论2：可以维护相邻结论2：可以维护相邻 最最优优决决策策取取队队尾尾元元素素策策满满足足：应应该该维维护护队队列列中中相相邻邻决决综综上上：isaTTTjjjjjjkk*2,.,1322125例5.APIO2010特

25、别行动队 。总时间复杂度为：最优决策在队尾。；或者个数小于下去，直到队列中元素，循环做，则删除队尾元素，如果取队尾两个决策加入队尾；：把新的可选决策或者列中的元素个数小于。循环做下去，直到队则删除队尾元素如果策每次选队列最后两个决要插入新的可选决策nOisaTisaTiiTTiTTijjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkk取取尾尾删删尾尾：插插入入删删尾尾：*2,2*2,2,111111 步：分以下递增所以具体程序实现由于，坐标是插入点，相当于在二维平面中插入一个新的决策计算枚举维护相邻决策满足：的整个过程中，始终要在计算4,1,*2,.,13221ixigisiiif

26、iisaTTTfjjjjjjkk程序实现：程序实现：26二.斜率优化总结 都是单调的。和以上斜率不等式中是后加入的决策点设为了便于分析，我们假或如的不等式：到关于斜率的优劣，使参数分离得对比两个可选决策状态转移方程能通过igixigxxyyigxxyyTjjjjjjjjjjjjjjj221121212122121,两个使用前提：两个使用前提：27二.斜率优化总结 。，最优决策取队首元素满足：维护队列中的相邻决策单调减：，最优决策取队尾元素满足：维护队列中的相邻决策单调增：，最优决策取队尾元素满足：维护队列中的相邻决策单调减：，最优决策取队首元素满足：维护队列中的相邻决策单调增：，种情况：的单调

27、性”分为以下四”和“还是经总结，根据“jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkTTTigigigTigTTTigigTigTTTigigTTTTigigigTgigTigT,.,;,.,;,.,;,.,13221211322121132212113221212121,四四种种情情况况：28三.斜率优化 。是单调的，以上斜率不等式中或如式。到一个类似斜率的不等的优劣，使参数分离得比两个可选决策状态转移方程能通过对不是单调的i但gixigigxxyyTjjjjjjjj12122121,29例6.游戏 庆语其庆语其验学校验学校出题人：北师大附属实出题人

28、：北师大附属实数据范围：数据范围：样例输出：样例输出：样例输入：样例输入：输出格式：输出格式：输入格式：输入格式：题目描述：题目描述：。的数据，对于的数据，对于最多能得到的分数。一个整数，表示。个数表示其中第个整数。第二行有第一行一个整数分。想知道他最多能得多少，没有分。有分数。他现在在原点上的所有分数，原点没现给出上。，他最后必须停在点上的分数，且要求是其中的分数，他将得到顶到顶，同时如果他从游戏里他只能向正方向他在玩一个游戏，这个顶到任意整点上。现在顶到更远的地方，他能的头变多了，于是他能现在内的数轴上的整点上。之隔在整点可以顶到与自己相化到数轴上，即从一个点上。我们现在将之简一个整点顶到

29、另一个整的位移，也就是从顶出前水平有限，每次只能是会造成位移的。他之从小就爱乱顶，但是顶500 ,100000%100;1000%6050111503,1)(*,jannWYFiainnWYFnnijjjaijjajiWYFkkWYF30例6.游戏 jjjjjjjjjjjjjjjjjjjjjjjnkkkTTTiaxxfxxiaffTiaiiafiaiiafjiiajOijjiiajfifijiif,.,.,1,*600 ,*max1322121121221112212212要满足：可选决策队列中从小到大排列的。即：之间的斜率是单调减的法可以得出，相邻决策采用前面两题类似的方还是有的！策之间的斜

30、率的单调性就不存在了，但相邻决中的结论类似于斜率优化不是单调的！是递增的，但横坐标的坐标是形式，决策不等式左边也是斜率的优？比，什么情况下策没有分离，考虑两个决和，有一项是分。，直接做时间复杂度为方程：的，得到以下状态转移顶到考虑最后一次是从的最大得分。表示从原点顶若干次到动态规划：分分析析：31例6.游戏 nnOiaTiaTTTTiaiaTiaTTTiaTifjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjxxxxxxxkxxxkkxxxxxxxxxxxxxxxxxkln,.,.,.,.,.,11211211111211322111 -21时间复杂度为法就可以找

31、出率是单调减的，用二分因为相邻决策之间的斜就是最优决策，且满足因此只要都要优！比后面的优比都要优！比前面的优比。则有：假设最优决策是时队列中可选决策有计算分分法法求求最最优优决决策策方方法法一一：二二32例6.游戏 nnOlrxlyrjjjjllryllrxkrljjjififififififyxyxjjln312111,131*2131, 1,是的区间，时间复杂度也每次排除否则回到则直接比较找出答案，如果否则则如计算，取一开始可以使用三分法：峰的模型，单峰求极值所有决策点形成一个单在二维平面中画出点作为纵坐标，对应的得分作为横坐标，把决策把队列中的可选决策：三三分分法法求求最最优优决决策策方

32、方法法二二好点好点坏点坏点33例6.游戏的时间复杂度也是值计算一次决策点对应的的区间，每次三分只需每次删除即：右的决策点。在新的有效区间中是靠右边的无效区间，是坏点，删除如果左的决策点；在新的有效区间中是靠左边的无效区间，是坏点，删除如果并满足以下两个要求：的比例固定，与和靠右决策点选择靠左决策点长度为另一种三分法，总区间：nOllylxyxlyxlxylxxyyyxxlyxyxlln*25-3*215*25-3,黄黄金金分分割割三三分分法法求求最最优优决决策策方方法法三三Lxy34四.斜率优化 或最左边策点不一定插在最右边不单调时，插入新的决。但以上斜率不等式中或如式。到一个类似斜率的不等的

33、优劣，使参数分离得比两个可选决策状态转移方程能通过对ixigigxxyyTjjjjjjjj都不是单调的i和gix12122121,35例7.NOI2007货币兑换券。次卖出操作卖出所有金操作使用完所有钱；每卖方案满足：每次买进必然存在一种最优的买，：位小数。答案保留得的最大的金钱数目。天的操作结束时能够获，表示第只有一个实数。、行三个实数行，第接下来时拥有的钱数。能预知的天数以及初始分别表示小、第一行两个正整数元钱。天后最多能够获得多少元钱，那么，如果开始时拥有他还希望能够计算出来。券的价值以及券和天内的经知道了未来运作和行情测算，他已员工，通过较长时间的时一个很有经济头脑的小行多次操作。注意

34、：同一天内可以进；天恰好为例在第券的比券和供给顾客的的金券，并且，满足提兑换给用户总价值为元人民币，交易所将会买入金券：顾客支付为人民币；券以当时的价值兑换的券和的为：将作为卖出比例，其意义内的实数个卖出金券：顾客提供一两个方面：易法。比例交易法分为便的交易方式：比例交易所提供了一种非常方为了方便顾客，金券交。单位金券元和券的价值分别为券和天中第人民币数目。我们记录位金券当天可以兑换的当时的价值，即每一单动，两种金券都有自己每天随着市场的起伏波数。券的数目可以是一个实有一个自己的账户。金每个持有金券的顾客都。券以前简称纪念券和券以下简称纪念券发行交易两种金券：工作。该金券交易所只最近在一家金券

35、交易所小提提示示：数数据据规规模模和和约约定定：输输出出格格式式：输输入入格格式式：题题目目描描述述：109,1000 ,100100 ,000100%100;1000%60;10%403,)%100, 0)/()()(MaxprofitNNNNMaxprofitKNYSNNSRateBANYKBAIPIPbBOPAOPOPaBAkBBAAYRateBARateBARateBAkkkkkkkkk36例7.NOI2007货币兑换钱？天后用户最多拥有多少元钱，问初始时用户拥有。两种金券的比例为、值的金券，买入的用所有的钱买入等价卖出所有的金券；如下操作：每一天用户进行若干次、分别具有单位价值、天天

36、内，第接下来的两种金券进行交易。、金券交易所可以对NSBABAiNBARateBAiii,问题简述：问题简述：么不卖要么全卖。操作也是完全的，即要类似的，可以证明卖出么不买要么全部买进；也就是说，买进操作要能使获利最大化时，取当能使获利最大化时，取当，则最后总利润买进时使用钱的比例为。利为一元钱不买金券最后获券到最后会获利为券和元，假定一元钱买进的，假设有在进行买进操作的时候01*1*,xqpxqpxqpqSqxSpxSxqpBAS提示的证明：提示的证明：37例7.NOI2007货币兑换 分。，间复杂度为可以用搜索来解决，时全部卖出进全部卖出后再全部买全部买进不进行活动种：动有以下出每一天可能

37、进行的活根据上面的提示，总结404nO4 4方方法法一一：搜搜索索38例7.NOI2007货币兑换 分。，直接做时间复杂度为时下状态转移方程：根据上面的分析，得以获利”这个子问题。天的最大第天卖出，这就涉及到“再在第天的最大获利全部买入第这样实际上就是要求把没有进行任何操作。天到第天，即第一次买入操作发生在第全部卖出：假设最后；进：这种操作没有意义全部卖出后再全部买没有意义；全部买进：这种操作天的最大获利；利等于第不进行活动：最大获天可以进行的活动：考虑第天的最大获利表示前状态601*1max1,1111,2nBARateBARateOijjfifiSifjNjNjjiiSfiifjjjiij

38、方方法法二二：动动态态规规划划39例7.NOI2007货币兑换 jjjjjjjjjRateRatejRatejjjABjjRatejRatejjjjjjjBARatejRatejBjARatejBjARatejjjjjBARateBARateBARateBARatekkkjiiiiiiiiiijjjjjjjiijTTTjgjgjjgjgggggjgjgTggjgggjgjggjggjgjgjgjfjgjijf,.,.,*,*,*,*11,*132212112121212211221121122122112121212，利用前面所学易知：序列标从小到大排序得决策把所有决策点按照横坐，纵坐标是的横

39、坐标是的形式，决策点以上不等式左边是斜率时，得：时，得：没有单调性：更优？比什么情况下、分析两个决策则上式设枚举到因为要从这里以上方程主要慢在方方法法三三：斜斜率率优优化化40例7.NOI2007货币兑换分。，时间复杂度为介绍。中的二分法，这里不再可以采用例不单调，寻找最优决策因为都可以。或可以用平衡树来维护，。右边的维护类似。或者满足个决策点少于，重复执行直到左边的则删除，如果的前一个决策点和决策点的前一个次找其中左边的维护可以每要保证斜率是递减的，的左边和右边，两边都并分别维护插入不用插入，否则进行出现了斜率上升，如果右边的决策左边的决策找到的操作如下：插入一个新决策间的斜率单调递减！然后再维护相邻决策之中间，尾，有可能会插在队列点时不可以直接插在队不单调时，插入新决策100ln6,2,1121112