一类单调问题的求解

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

2、3 day5 79 8080 7875，既新鲜又美味，既新鲜又美味 8080 79737978 day5-day1=4天天 79 一.单调队列及应用 3 WC2016WC2016绵阳南山绵阳南山 。队列中的最大值在队首中维护单调减的队列，如例 中是单调减的。素是单调的，如例由得队列中保留的元 直接删除。没有存在的必要，可以 比“既新鲜又美味”，跟，且，如果满足与中，区间中两个元素如例 右移向右平移的。递增。查询区间是随着时，非递减，当左边界 递增，的增加，右边界。随着，右边界中，区间左边界如例 ，天选择的苹果的美味度表示老徐第天发放苹果的美味度，表示第中，设如例 0 0 最最优优选选择择在在队

3、队首首： 保保持持队队列列单单调调： 去去除除冗冗余余状状态态： 区区间间出出现现平平移移： 维维护护区区间间最最值值： 五五大大要要点点： 0 0 1, 1max0 1, 1maxmax 0 a aaaaaa ll rrl a a j jkjkkj ii iii j i jk iMi iiMi ijMiif iifi 一.单调队列及应用 4 WC2016WC2016绵阳南山绵阳南山 结构。优于堆或线段树等数据时间复杂度为进出队列各一次，所以由于每个元素最多只会 最优答案在队首 插入元素 删除队首元素 删除队尾元素 中的代码如下：例 , ; ;: ;: );( );( );()( 1: ; 0

4、:; 1: 0 NO end stqaif iienqeninc stincthenMstqiif endecdoenqaiaandstenwhile begindontoifor enst 代码实现：代码实现： 例1.NOIP2010初赛烽火传递 5 WC2016WC2016绵阳南山绵阳南山 。，的数据，对于 的数据，对于 一行，表示答案。 代价。个烽火台发出信号所需，表示第行，每行一个数接下来 个发出信号。个烽火台中至少要有一表示在连续表示烽火台的个数，。其中第一行：两个整数 。座城市之间准确出传递袭之时，情报能在这两少代价，才能使敌军来请计算总共最少花费多 个发出信号。个烽火台中至少要有

5、一连续使情报准确地传递，在号都有一定代价。为了 发出信个烽火台，每个烽火台之间有递军情，在某两座城市晚燃烧干柴，以火光传通过浓烟表达信息；夜 白天燃烧柴草，上。一旦有敌情发生，般建在险要或交通要道要的军事防御设施，一烽火台又称烽燧，是重 100000100%100 ;1000%50 2 6 5 2 1 435 , W W i i NM NM iN MMNMN M N 数据范围：数据范围： 样例输出：样例输出：样例输入：样例输入： 输出格式：输出格式： 输入格式：输入格式： 题目描述：题目描述： 例1.NOIP2010初赛烽火传递 6 。间复杂度为使用单调队列优化，时 在队首。持单调递增，最优决

6、策，所以队列中的元素保删除 ，可以且，如果而且区间是向右平移的时要计算区间最小值，上式计算 答案 时 时 程：”得到以下状态转移方台的位置通过考虑“前一个烽火 ”所需最小代价。个烽火台一定发出信号个烽火台传递情报且第表示“在前动态规划：状态 NO jf jkjfkfif NiMNifAns MiijMijf Mi if j iiif w w i i 1 ,1maxmin 1min 分析：分析： WC2016WC2016绵阳南山绵阳南山 例2.GDKOI2009猴子 。，： 吃到的香蕉数。个整数，为猴子最多能输出只有一行，包含一 。总是位置。并且没有两棵树在同一 从近到远排列。输入保证这些树按照

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

8、MNM NMDN ba b ba ii ii 数数据据范范围围： 样样例例输输出出：样样例例输输入入： 输输出出格格式式： 输输入入格格式式： 题题目目描描述述： 7 WC2016WC2016绵阳南山绵阳南山 例2.GDKOI2009猴子 8 。时间复杂度为 最优值在队首。 调递减的队列。移的，可以维护一个单的增加，区间是向下平值，同一列随着 大列的连续元素的区间最时需要计算第，计算按照列从小到大来处理 答案 时且其中 时 ：得到以下状态转移方程点考虑最后一次跳跃的起 。棵树最多能吃多少香蕉次跳跃跳到第棵树不超过表示从第动态规划：状态 NMO i jjif MNfAns jDikjkf i j

9、if k ijjif bba a kii 1, , 1 1101,max 0 , 1, 0 分析：分析： WC2016WC2016绵阳南山绵阳南山 i j-1j 例3.多重背包 9 且价值总和最大。 不超过背包容量，使这些物品的体积总和。选择物品装入背包可价值是 ，件可用，体积是种物品最多有的背包。第种物品和一个容量为有 w vm i ii iVN WC2016WC2016绵阳南山绵阳南山 例3.多重背包 10 ：分别用蓝色和红色标记要用到的元素示意图，和观察计算 这里不做介绍当然用倍增法优化到时间复杂度为 下状态转移方程：个物品装几个”得到以通过考虑“第 值。个物品能获得的最大价的背包来装前

10、表示用容量为背包问题，定义状态 v m v mwv i N i N i i i iii jifjif m VOVO j xxxjif i jif i ijjif i , ,*,* ,min0*, 1 00 , , 1 2 1 log 分析：分析： WC2016WC2016绵阳南山绵阳南山 i j i-1 j-vij+vi 例3.多重背包 11 NVO j ji kkkjifkkkjif kkkjifjif kjifjifjif jif jifjif jif v vv xxx wxvxvwxvxv xxxvx vxwxvxwxvx xxxx v v i ii iiiiii i iiiii i i

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

12、1 11122 1221 程序实现：程序实现： 去除冗余保持单调：去除冗余保持单调： 区间出现平移：区间出现平移： 维护区间最值：维护区间最值： 分析：分析： WC2016WC2016绵阳南山绵阳南山 例4.HNOI2008Toy 12 10 7 2 ,1 ,500001 4 1 2 4 3 145 1 1 8 c c Lx c c i i j ik k i LN NLN L PLx Pijxji PODZiNN PODZODZ PP 数据范围：数据范围： 样例输出：样例输出：样例输入：样例输入： 输出格式：输出格式： 输入格式：输入格式： 题目描述：题目描述： 输出最小费用。 。行输入，接下

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

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

15、jsisji c O jj jxigjijf jxigjfjf jjsjjxLisiig jsjjfjLisiif ijjfif iji isiif j j i 2 112 22 222 2 , *2,1 *211 ,1, 1,1, 1,1min 12 1 分析：分析： WC2016WC2016绵阳南山绵阳南山 例4.HNOI2008Toy 14 WC2016WC2016绵阳南山绵阳南山 斜率优化！题要用到新知识：两个点形成的斜率，这，上面式子左边像 ：是单调递增的，所以有因再令 jj jj jj ix jjjxjjxj igjjxjigjjxj ig xx yy isiixifiy xxig

16、ff xigfxigf 21 12 12 2 12 2 1 2 2 2 1 2 1 2 2 2 2 *2 )()( )()( 1,1 *2 1 1- 2 1 *2 1 1*2 2 1 的前提条件：的前提条件： j jj j 时时研究研究 i if fi if fj jj j 1 12 2 1 12 2 例4.HNOI2008Toy 15 WC2016WC2016绵阳南山绵阳南山 的结论：增的。下面有两个重要都是单调的，都是单调和该题 则必须满足优，令比，如果时，可选决策计算 igix igT xx yy Tif jj jj jj jjjjjj *2, )()( )()( , 21 12 12

17、211212 斜斜率率优优化化： 再继续维护！列基础上加入新的决策时可以在之前维护的队并且在 是最优的！优。所以队首比优，比优，比来说，则对于 所以 可以删除。优，永远比时，有：，计算后面的 是单调增的，则对于由于之间的斜率策如果队列中相邻两个决 。 。， , 11 ., *2,.,*2,*2, *2*2, ,*2, *2,.,*2,*2, *2,., 113221 13221 1111 113221 21 iif if igTigTigT xxygigyxTfi igigyxTyx igTigTigT ig if jjjjjjj jjjjjj iiii jjjjjjj jjj kk kk k

18、k k 证证明明： 最最优优决决策策是是队队首首元元素素 即即：的的斜斜率率都都要要大大于于使使得得这这些些相相邻邻决决策策之之间间决决策策依依次次存存储储有有价价值值的的可可选选 大大策策，使使得得队队列列中中从从小小到到可可以以删删除除其其中中的的冗冗余余决决 到到i i, ,时时，所所有有可可选选决决策策是是1 1结结论论1 1：计计算算 例4.HNOI2008Toy 16 WC2016WC2016绵阳南山绵阳南山 j1 j2 j3 可以删除。得证！不可能成为最优决策，出现了矛盾！所以 优比 优比 。的过程中成为最优决策有没有可能在计算，分析即 。邻斜率单调递减的情况，假设出现下图所示相

19、设队列中三个相邻决策 jjjjj jjjj jjjj jjjjj jjj TigT igT igT fTT 22132 3232 2112 23221 321 ,*2, *2, *2, , 证明：证明： 决策之间的斜率单调增决策之间的斜率单调增结论2：可以维护相邻结论2：可以维护相邻 最最优优决决策策取取队队首首元元素素 策策满满足足：应应该该维维护护队队列列中中相相邻邻决决 综综上上 ： jjjjjj kk TTTig,.,*2 13221 例4.HNOI2008Toy 17 WC2016WC2016绵阳南山绵阳南山 ：最优决策在队首。 ；或者于直到队列中元素个数小 ，循环做下去，则删除队首

20、元素，如果取队首两个决策 加入队尾；：把新的可选决策 或者列中的元素个数小于。循环做下去，直到队则删除队尾元素 如果策每次选队列最后两个决要插入新的可选决策 取取头头 删删头头： 插插入入 删删尾尾： igT igT i iTT iTTi jj jjjjj jjjj jjjjj kkkk kkkkk *2,2 *2, ,2 , 21 12121 1 11 步：下所以具体程序实现分以 递增由于，坐标是插入点，相当于在二维平面中插入一个新的决策计算枚举 维护相邻决策满足：的整个过程中，始终要在计算 4 , ,.,*2 13221 ixiyixiiifi TTTigf jjjjjj kk 程序实现：

21、程序实现： 例4.HNOI2008Toy 18 WC2016WC2016绵阳南山绵阳南山 动画演示：动画演示： j1 j2 j3 j4 j5 T(j3,j4)T(j4,j5) T(j2,j3)T(j3,j5) T(j1,j2)2g(i) 最优决策为最优决策为j2 例4.HNOI2008Toy 19 WC2016WC2016绵阳南山绵阳南山 nO end istqtstqfif stincdoigstqstqtandenstwhile ienqeninc endecdoienqtenqenqtandenstwhile begindontoifor enstf 时间复杂度为 取头 删头 插入 去尾

22、 ; );,(cos 1: );()*2)1,() 1( ;: );( );(),),1() 1( 1: ; 0:; 1:; 0: 0 程序代码：程序代码： 例5.APIO2010特别行动队 20 的战斗力和更大。 正后，没有其他方案能使修。修正后的战斗力和为为，修正后的战斗力分别战斗力分别为 。特别行动队的初始，第三队包含士兵，第二队包含士兵和士兵含士兵特别行动队：第一队包 个士兵组成。此时，最佳方案是将。经验公式中的参数为 名士兵，和。例如你有最大。试求出这个最大动队修正后战斗力之和编队，使得所有特别行 你要为这支部队进行。作为部队统帅，现在是已知的系数其中式修正为 将按如下经验公的初始战

23、斗力总结出一支特别行动队。通过长期的观察，你 之和，即为对内士兵初始战斗力战斗力一支特别行动队的初始的士兵的初始战斗力为编号为 的序列。即为形如队员的编号应该连续，同一支特别行动队中战场。出于默契的考虑 若干特别行动队调入编号，要将他们拆分成到队，士兵从名预备役士兵组成的部你有一支由 94 , 1 , 44 , 3 , 4 4321 320,10, 14, 3, 2 , 24 )0(, . , ),.1,( 1 432 1 2 1 cba acbacbxax xx xi kiii nn xxx x x xxx x kiii i 题目描述：题目描述： WC2016WC2016绵阳南山绵阳南山 1

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

25、 2 1 1 1 1 n isjs isjs jsis jsis x O ijjsisaihjgif jijsisa cisbaihjsbajfjg cisbajsisajsbajf jiji cjsbisbajsisaajf ijcjsisbajfif ji is iif i 分析：分析： WC2016WC2016绵阳南山绵阳南山 例5.APIO2010特别行动队 22 上一题用斜率优化！是单调的，可以考虑像 的坐标是 的坐标是中两个点形成的斜率，其，上面式子左边像 上式得： 是单调增的是正整数，因初始战斗力 ：时 is gs gs isa ss gg is ssisagg sisaihgs

26、isaihg jj jjj jjjjj jj jj xx jjjj jjjj ififjj i j ji 222 11121 12 12 1 1212 1122 12 ,1 ,1 *2 11 11*2 1*21*2 12 的前提条件的前提条件研究研究 WC2016WC2016绵阳南山绵阳南山 例5.APIO2010特别行动队 23 WC2016WC2016绵阳南山绵阳南山 个重要的结论：是单调增的，同样有两该题 优，必须满足要比时换句话说， 优，必须满足比。如果，令时，可选决策根据上面分析：计算 is isaT isaT ss gg Tif jjjjjj jj jj jj jj jjjj *2

27、, *2, 11 , 212121 21 12 12 12 2112 应用斜率优化：应用斜率优化： 是最优的！优。所以队尾元素比，优，比优，比 所以 可以删除优，永远比时，有：，计算对于后面的 是单调增的，优。由于比之间的斜率策如果队列中相邻两个决 。 。 ， jjjjjjj jjjjjj iiii jjj jjjj jjj kkk kk kkk k isaTisaTisaT yyxsaisayxTfi isyxisayxTyx isaT isaTisaTisa if 1 -2312 13221 1111 1 3221 21 . *2,.,*2,*2, *2*2, ,*2, *2, .,*2,

28、*2,*2 ,., 证证明明： 最最优优决决策策是是队队尾尾元元素素 即即：大大于于相相邻邻决决策策之之间间的的斜斜率率都都 依依次次存存储储可可选选决决策策，使使得得队队列列中中从从小小到到大大时时，可可以以删删除除冗冗余余决决策策结结论论1 1：计计算算 例5.APIO2010特别行动队 24 WC2016WC2016绵阳南山绵阳南山 可以删除。得证！不可能成为最优决策，出现了矛盾！所以 优比 优比 。的过程中成为最优决策有没有可能在计算，分析即 。邻斜率单调递增的情况，假设出现下图所示相设队列中三个相邻决策 jjjjj jjjj jjjj jjjjj jjj TisaT isaT isa

29、T fTT 23221 3232 2112 23221 321 ,*2, *2, *2, , 证明：证明： 决策之间的斜率单调减决策之间的斜率单调减结论2：可以维护相邻结论2：可以维护相邻 最最优优决决策策取取队队尾尾元元素素 策策满满足足：应应该该维维护护队队列列中中相相邻邻决决 综综上上 ： isaTTT jjjjjj kk *2,., 13221 例5.APIO2010特别行动队 25 WC2016WC2016绵阳南山绵阳南山 。总时间复杂度为 ：最优决策在队尾。 ；或者个数小于下去，直到队列中元素 ，循环做，则删除队尾元素，如果取队尾两个决策 加入队尾；：把新的可选决策 或者列中的元素

30、个数小于。循环做下去，直到队则删除队尾元素 如果策每次选队列最后两个决要插入新的可选决策 nO isaT isaT i iTT iTTi jj jjjjj jjjj jjjjj kk kkkkk kkkk kkkkk 取取尾尾 删删尾尾： 插插入入 删删尾尾： *2,2 *2, ,2 , 1 11 1 11 步：分以下递增所以具体程序实现由于 ，坐标是插入点，相当于在二维平面中插入一个新的决策计算枚举 维护相邻决策满足：的整个过程中，始终要在计算 4 ,1, *2,., 13221 ix igisiiifi isaTTT f jjjjjj kk 程序实现：程序实现： 二.斜率优化总结 WC20

31、16WC2016绵阳南山绵阳南山 26 都是单调的。和以上斜率不等式中 是后加入的决策点设为了便于分析，我们假 或如 的不等式： 到关于斜率的优劣，使参数分离得对比两个可选决策状态转移方程能通过 igix ig xx yy ig xx yy T jjj jj jj jj jj jj jj 221 12 12 12 12 21 21 , , 两个使用前提：两个使用前提： 二.斜率优化总结 WC2016WC2016绵阳南山绵阳南山 27 。，最优决策取队首元素满足：维护队列中的相邻决策 单调减：， ，最优决策取队尾元素满足：维护队列中的相邻决策 单调增：， ，最优决策取队尾元素满足：维护队列中的相

32、邻决策 单调减：， ，最优决策取队首元素满足：维护队列中的相邻决策 单调增：， 种情况：的单调性”分为以下四”和“还是经总结，根据“ jjjjjj jj jjjjjj jj jjjjjj jj jjjjjj jj jjjj kk kk kk kk TTTig igigT igTTT igigT igTTT igigT TTTig igigT gigTigT ,., ;,., ;,., ;,., , 13221 21 13221 21 13221 21 13221 21 2121 , , , , 四种情况：四种情况： 三.斜率优化 WC2016WC2016绵阳南山绵阳南山 28 。是单调的，以上

33、斜率不等式中 或如 式。到一个类似斜率的不等的优劣，使参数分离得比两个可选决策状态转移方程能通过对 不是单调的i但gix igig xx yy T jj jj jj jj 12 12 21 21 , 例6.游戏 WC2016WC2016绵阳南山绵阳南山 29 庆语其庆语其验学校验学校出题人：北师大附属实出题人：北师大附属实 数据范围：数据范围： 样例输出：样例输出：样例输入：样例输入： 输出格式：输出格式： 输入格式：输入格式： 题目描述：题目描述： 。的数据，对于 的数据，对于 最多能得到的分数。一个整数，表示 。个数表示其中第个整数。第二行有第一行一个整数 分。想知道他最多能得多少，没有分

34、。有分数。他现在在原点上的所有分数，原点没现给出 上。，他最后必须停在点上的分数，且要求是其中 的分数，他将得到顶到顶，同时如果他从游戏里他只能向正方向他在玩一个游戏，这个 顶到任意整点上。现在顶到更远的地方，他能的头变多了，于是他能现在内的数轴上的整点上。 之隔在整点可以顶到与自己相化到数轴上，即从一个点上。我们现在将之简一个整点顶到另一个整 的位移，也就是从顶出前水平有限，每次只能是会造成位移的。他之从小就爱乱顶，但是顶 500 ,100000%100 ;1000%60 5011 1503 , 1 )(*, jan n WYF iainn WYFn nijjja ijjaji WYF k

35、kWYF 例6.游戏 WC2016WC2016绵阳南山绵阳南山 30 jjjjjjjjj jj jj jj jjjj jjjj n kkk TTT iaxxfxx ia ff T iaiiafiaiiaf jiiaj O ijjiiajfif ij iif ,.,., 1 , , * * 60 0 ,*max 1322121 12 12 21 1122 1221 2 要满足：可选决策队列中从小到大排列的 。即：之间的斜率是单调减的法可以得出，相邻决策采用前面两题类似的方 还是有的！策之间的斜率的单调性就不存在了，但相邻决中的结论类似于斜率优化 不是单调的！是递增的，但横坐标的坐标是形式，决策不

36、等式左边也是斜率的 优？比，什么情况下策没有分离，考虑两个决和，有一项是 分。，直接做时间复杂度为 方程：的，得到以下状态转移顶到考虑最后一次是从 的最大得分。表示从原点顶若干次到动态规划： 分分析析： 例6.游戏 WC2016WC2016绵阳南山绵阳南山 31 nnO iaTiaT TTTia iaT iaTTT iaT if j jjjjjj jjjj jjjjjj jjjj jjjj jjjjjj jjjj jjjj x xxxxxx kxxx kkxxxx xxxx xx xx xxxx xk ln , ,., ,., , ,., ,., , ,., 11 21 1211 11 121

37、 13221 11 - 21 时间复杂度为 法就可以找出率是单调减的，用二分因为相邻决策之间的斜 就是最优决策，且满足因此只要 都要优！比后面的 优比 都要优！比前面的 优比 。则有：假设最优决策是时队列中可选决策有计算 分分法法求求最最优优决决策策方方法法一一：二二 例6.游戏 WC2016WC2016绵阳南山绵阳南山 32 nnO lr xlyr jj jj l lr yl lr x krl j jj ifif ifif if if yx yx j j ln 3 1 21 11 , 1 3 1*2 1 3 1 , 1 , 是的区间，时间复杂度也每次排除 否则回到则直接比较找出答案，如果 否

38、则则如 计算 ，取 一开始 可以使用三分法：峰的模型，单峰求极值所有决策点形成一个单 在二维平面中画出点 作为纵坐标，对应的得分作为横坐标，把决策把队列中的可选决策 ： 三三分分法法求求最最优优决决策策方方法法二二 好点好点 坏点坏点 例6.游戏 WC2016WC2016绵阳南山绵阳南山 33 的时间复杂度也是 值计算一次决策点对应的的区间，每次三分只需每次删除 即： 右的决策点。在新的有效区间中是靠右边的无效区间，是坏点，删除如果 左的决策点；在新的有效区间中是靠左边的无效区间，是坏点，删除如果 并满足以下两个要求： 的比例固定，与和靠右决策点选择靠左决策点长度为另一种三分法，总区间 ： n

39、O l ly lx y x l y xl xy l x xyy yxx lyxyxl ln * 2 5-3 * 2 15 * 2 5-3 , 黄黄金金分分割割三三分分法法求求最最优优决决策策方方法法三三 L x y 四.斜率优化 WC2016WC2016绵阳南山绵阳南山 34 或最左边策点不一定插在最右边不单调时，插入新的决 。但以上斜率不等式中 或如 式。到一个类似斜率的不等的优劣，使参数分离得比两个可选决策状态转移方程能通过对 ix igig xx yy T jj jj jj jj 都不是单调的i和gix 12 12 21 21 , 例7.NOI2007货币兑换 WC2016WC2016绵

40、阳南山绵阳南山 35 券。次卖出操作卖出所有金操作使用完所有钱；每卖方案满足：每次买进必然存在一种最优的买 ，： 位小数。答案保留得的最大的金钱数目。天的操作结束时能够获，表示第只有一个实数 。、行三个实数行，第接下来时拥有的钱数。能预知的天数以及初始分别表示小、第一行两个正整数 元钱。天后最多能够获得多少元钱，那么，如果开始时拥有他还希望能够计算出来 。券的价值以及券和天内的经知道了未来运作和行情测算，他已员工，通过较长时间的时一个很有经济头脑的小 行多次操作。注意：同一天内可以进 ；天恰好为例在第 券的比券和供给顾客的的金券，并且，满足提兑换给用户总价值为元人民币，交易所将会买入金券：顾客

41、支付 为人民币； 券以当时的价值兑换的券和的为：将作为卖出比例，其意义内的实数个卖出金券：顾客提供一 两个方面：易法。比例交易法分为便的交易方式：比例交易所提供了一种非常方为了方便顾客，金券交 。单位金券元和券的价值分别为券和天中 第人民币数目。我们记录位金券当天可以兑换的当时的价值，即每一单动，两种金券都有自己每天随着市场的起伏波 数。券的数目可以是一个实有一个自己的账户。金每个持有金券的顾客都 。券以前简称纪念券和券以下简称纪念券发行交易两种金券：工作。该金券交易所只最近在一家金券交易所小 提提示示： 数数据据规规模模和和约约定定： 输输出出格格式式： 输输入入格格式式： 题题目目描描述述

42、： 10 9 ,1000 ,100100 ,000100%100;1000%60;10%40 3 , ) %100, 0) )/( )()( MaxprofitNNN NMaxprofit KNYSN NS RateBANY K BAIPIPb BOPAOPOPa BAk BBAAY RateBA RateBA Rate BA kkk kkk k kk 例7.NOI2007货币兑换 WC2016WC2016绵阳南山绵阳南山 36 钱？天后用户最多拥有多少元钱，问初始时用户拥有 。两种金券的比例为、值的金券，买入的用所有的钱买入等价 卖出所有的金券； 如下操作：每一天用户进行若干次、分别具有单位

43、价值、天天内，第接下来的 两种金券进行交易。、金券交易所可以对 NS BA BAiN BA Rate BA i ii , 问问题题简简述述： 么不卖要么全卖。操作也是完全的，即要类似的，可以证明卖出 么不买要么全部买进；也就是说，买进操作要 能使获利最大化时，取当能使获利最大化时，取当 ，则最后总利润买进时使用钱的比例为 。利为一元钱不买金券最后获 券到最后会获利为券和元，假定一元钱买进的，假设有在进行买进操作的时候 01 *1* , xqpxqp xqpqSqxSpxSx q pBAS 提示的证明：提示的证明： 例7.NOI2007货币兑换 WC2016WC2016绵阳南山绵阳南山 37 分

44、。，间复杂度为可以用搜索来解决，时 全部卖出 进全部卖出后再全部买 全部买进 不进行活动 种：动有以下出每一天可能进行的活根据上面的提示，总结 40 4 n O 4 4 方方法法一一：搜搜索索 例7.NOI2007货币兑换 WC2016WC2016绵阳南山绵阳南山 38 分。，直接做时间复杂度为 时 下状态转移方程：根据上面的分析，得以 天的最大获利表示前动态规划：状态 获利”这个子问题。 天的最大第天卖出，这就涉及到“再在第天的最大获利全部买入第这样实际上就是要求把 没有进行任何操作。天到第天，即第一次买入操作发生在第全部卖出：假设最后 ；进：这种操作没有意义全部卖出后再全部买 没有意义；全

45、部买进：这种操作 天的最大获利；利等于第不进行活动：最大获 的活动：考虑最后一天可以进行 60 1 * * * 1 max 1, 1, 11 1 2 n BARate BARate O ijjf if iS if Sfiif jNj Njj N jjj iij 方方法法二二：动动态态规规划划 例7.NOI2007货币兑换 WC2016WC2016绵阳南山绵阳南山 39 jjjjjj jjj Rate RatejRatejjj A B jj RatejRatej jjjj jj BARate jRatej B j ARate j B j ARate j jjjj BARate BARate BA

46、Rate BARate kk k j i i ii iiii iij jjj jjj iij TTT jgjgj j g j ggg gg j g j g Tgg jg gg j g j g g j gg j g jgjg jf jg jijf ,., ,., * * * , * * , *, * 11, * * * 13221 21 1212 12 12 2112 2112 1122 1221 12 12 12 12 ，利用前面所学易知：序列标从小到大排序得决策把所有决策点按照横坐 ，纵坐标是的横坐标是的形式，决策点以上不等式左边是斜率 时，得： 时，得： 没有单调性： 更优？比什么情况下、

47、分析两个决策 则上式设 枚举到因为要从这里以上方程主要慢在 方方法法三三：斜斜率率优优化化 例7.NOI2007货币兑换 WC2016WC2016绵阳南山绵阳南山 40 分。，时间复杂度为 介绍。中的二分法，这里不再可以采用例不单调，寻找最优决策因为 都可以。或可以用平衡树来维护， 。右边的维护类似。或者满足 个决策点少于，重复执行直到左边的则删除，如果的前一个决策点和决策点 的前一个次找其中左边的维护可以每要保证斜率是递减的，的左边和右边，两边都并分别维护插入 不用插入，否则进行出现了斜率上升，如果右边的决策左边的决策找到 的操作如下：插入一个新决策 间的斜率单调递减！然后再维护相邻决策之 中间，尾，有可能会插在队列点时不可以直接插在队不单调时，插入新决策 100ln 6 , 2, , , 112 1112211 2121 nnO SplayTreap xTT xTT xxx xxTxTx x g A B xxx xxxxxxx xxxx i i 方方法法三三：斜斜率率优优化化 例7.NOI2007货币兑换 WC2016WC2016绵阳南山绵阳南山 41 j1 j2 j3 j4 j5 j6 j7 T(j2,