2一类单调问题的求解(宋新波128下午)

一类单调问题的求解中山纪念中学宋新波1WC2016绵阳南山例0.老徐真人秀WC2016绵阳南山2做到的？请老徐回答当时是怎么通过程序来快速选择。老徐是编程达人，决定天的最美味的苹果。只会吃天数不超过老徐有个怪癖，每一天干，供同一种美味的苹果若天，每一天节目组都提个真人秀，节目共录制最美杭城人老徐参加一1061NMMN随手扔过来下面这个：直接告诉你答案，当时老徐是大师，当然不会，老徐的做法如下：别为天提供的苹果美味度分，，比如，79,73,78,75,80545MNday180day275day378day473day57980807875，既新鲜又美味808079737978day5-day1=4天79一.单调队列及应用3WC2016绵阳南山。队列中的最大值在队首中维护单调减的队列，如例中是单调减的。素是单调的，如例由③得队列中保留的元直接删除。没有存在的必要，可以比“既新鲜又美味”，跟，且，如果满足与中，区间中两个元素如例右移向右平移的。递增。查询区间是随着时，非递减，当左边界递增，的增加，右边界。随着，右边界中，区间左边界如例，天选择的苹果的美味度表示老徐第天发放苹果的美味度，表示第中，设如例0⑤最优选择在队首：④保持队列单调：③去除冗余状态：②区间出现平移：①维护区间最值：五大要点：001,1max01,1maxmax0aaaaaaallrrlaajjkjkkjiiiiijijkiMiiiMiijMiifiifi一.单调队列及应用4WC2016绵阳南山结构。优于堆或线段树等数据时间复杂度为进出队列各一次，所以由于每个元素最多只会最优答案在队首插入元素删除队首元素删除队尾元素中的代码如下：例,;}{]];[[:][}{;:][);();(][}{);(]])[[][(1:;0:;1:0NOendstqaifiienqenincstincthenMstqiifendecdoenqaiaandstenwhilebegindontoiforenst代码实现：例1.[NOIP2010初赛]烽火传递5WC2016绵阳南山。，，的数据，对于的数据，对于一行，表示答案。代价。个烽火台发出信号所需，表示第行，每行一个数接下来个发出信号。个烽火台中至少要有一表示在连续表示烽火台的个数，。其中第一行：两个整数。座城市之间准确出传递袭之时，情报能在这两少代价，才能使敌军来请计算总共最少花费多个发出信号。个烽火台中至少要有一连续使情报准确地传递，在号都有一定代价。为了发出信个烽火台，每个烽火台之间有递军情，在某两座城市晚燃烧干柴，以火光传通过浓烟表达信息；夜白天燃烧柴草，上。一旦有敌情发生，般建在险要或交通要道要的军事防御设施，一烽火台又称烽燧，是重100000100%100;1000%5026521435,WWiiNMNMiNMMNMNMN数据范围：样例输出：样例输入：输出格式：输入格式：题目描述：例1.[NOIP2010初赛]烽火传递6。间复杂度为使用单调队列优化，时在队首。持单调递增，最优决策，所以队列中的元素保删除，可以且，如果而且区间是向右平移的时要计算区间最小值，上式计算答案时时程：”得到以下状态转移方台的位置通过考虑“前一个烽火”所需最小代价。个烽火台一定发出信号个烽火台传递情报且第表示“在前动态规划：状态NOjfjkjfkfifNiMNifAnsMiijMijfMiifjiiifwwii1,1maxmin1min分析：WC2016绵阳南山例2.[GDKOI2009]猴子。，：：：吃到的香蕉数。个整数，为猴子最多能输出只有一行，包含一。总是位置。并且没有两棵树在同一从近到远排列。输入保证这些树按照树到猴子所在树的距离上的香蕉数，以及这棵，分别表示每棵香蕉树个整数行每行包含两。下面最多跳跃次数距离，猴子每次跳跃的最大，分别是香蕉树的棵数输入第一行为三个整数多能吃多少个香蕉呢？香蕉都吃了。那么它最，它就会把那棵树上的。每当他跳到一棵树上得太远或跳的次数太多跳力也有限，它不能一次棵树上。同时猴子的体只想从一棵树跳到另一它又不想在地上走，而想吃尽量多的香蕉，但棵树上。这个猴子当然则在这排香蕉树的第一在同一直线上，而猴子蕉树，这些香蕉树都种一个猴子找到了很多香10000,,5000%100;2000%50;100%3010976543806202550,,0DNMNMNMNMDNbabbaiiii数据范围：样例输出：样例输入：输出格式：输入格式：题目描述：7WC2016绵阳南山例2.[GDKOI2009]猴子8。时间复杂度为最优值在队首。调递减的队列。移的，可以维护一个单的增加，区间是向下平值，同一列随着大列的连续元素的区间最时需要计算第，计算按照列从小到大来处理答案时且其中时：得到以下状态转移方程点考虑最后一次跳跃的起。棵树最多能吃多少香蕉次跳跃跳到第棵树不超过表示从第动态规划：状态NMOijjifMNfAnsjDikjkfijifkijjifbbaakii1,,11101,max0,1,0分析：WC2016绵阳南山ij-1j例3.多重背包9且价值总和最大。不超过背包容量，使这些物品的体积总和。选择物品装入背包可价值是，件可用，体积是种物品最多有的背包。第种物品和一个容量为有wvmiiiiVNWC2016绵阳南山例3.多重背包10：分别用蓝色和红色标记要用到的元素示意图，和观察计算这里不做介绍当然用倍增法优化到时间复杂度为下状态转移方程：个物品装几个”得到以通过考虑“第值。个物品能获得的最大价的背包来装前表示用容量为背包问题，定义状态vmvmwviNiNiiiiiijifjifmVOVOjxxxjifijifiijjifi,,,*,*,min0**,100,,121log分析：WC2016绵阳南山iji-1j-vij+vi例3.多重背包11NVOjjikkkjifkkkjifkkkjifjifkjifjifjifjifjifjifjifvvvxxxwxvxvwxvxvxxxvxvxwxvxwxvxxxxxvviiiiiiiiiiiiiiiii时间复杂度为空间。的值分批次处理以节省按照模当然也可以把的状态等于模对应背包容量个单调队列，其中队列建立一行来做，每一行需要从小到大来处理，一行按可以永久删除。优，还是比的，跟上面的不等式是等价，而不等式对应着同样的可选决策对应着的可选决策来说于后面的某一个状态可以直接删除。因为对时，且满足：如果时，对于两个可选决策计算在向右平移；区间相对时涉及到的元素组成的计算等距的元素，距离为时涉及的元素是上一行置连续的元素，如计算注意这里的区间不是位：活运用单调队列来优化由上图发现该题可以灵,00***,1***,1,*,,*,**,1**,1,,,,,,11211222211111221221④程序实现：③去除冗余保持单调：②区间出现平移：①维护区间最值：分析：WC2016绵阳南山例4.[HNOI2008]Toy121072,1,50000141243145118ccLxcciijikkiLNNLNLPLxPijxjiPODZiNNPODZODZPP数据范围：样例输出：样例输入：输出格式：输入格式：题目描述：输出最小费用。。行输入，接下来和第一行输入两个整数，但他希望费用最小。甚至超过意长度的容器，他可以制造出任教授不关心容器的数目是一个常量。，其中，其制作费用为度为授的研究，如果容器长教器长度有关，根据。制作容器的费用与容，那容器的长度将为件玩具放在一个容器中到第如果将第形式地说，个单位长度的填充物。玩具之间要加入个玩具，那么相邻两件果一个一维容器中有多号是连续的。同时，如器中的玩具编教授要求在一个一维容。为了方便整理，处理后一维长度是件玩具经过件玩具，第的到号为教授有编一维容器中。维，再装到一种特殊的可以将任意物品变成一来给玩具装箱。自己的物体维度压缩器教授使用北京去。决定把所有玩具都运到堆智力玩具。于是，他他割舍不下自己的一大教授要去看奥运，但是月WC2016绵阳南山例4.[HNOI2008]Toy13，超时。直接做时间复杂度为入的分析。的单调性，需要深就可以删除”这样明显没有前面几个例子中“却没有分离，的，这两个参数是完全分离和这三项中式子中则有对应的费用记为。可选决策定义离注意展开过程中参数分，是未知的，展开平方式的含有这些量相当于已知，而时，计算其中下状态转移方程：这段连续的玩具，得以到设是装在同一个容器中，假考虑哪些玩具与玩具的前缀和。为用，个玩具装箱所需最小费表示把前动态规划：状态njififjjigjxigjxjxigififLjsisjicOjjjxigjijfjxigjfjfjjsjjxLisiigjsjjfjLisiifijjfifijiisiifjji2112222222,,**2,,1**211,1,,1,,1,,1,1min121分析：WC2016绵阳南山例4.[HNOI2008]Toy14WC2016绵阳南山斜率优化！题要用到新知识：两个点形成的斜率，这，上面式子左边像：是单调递增的，所以有因再令jjjjjjixjjjxjjxjigjjxjigjjxjigxxyyisiixifiyxxigffxigfxigf211212212212221212222*2)()()()(1,1**211-21**211**221的前提条件：jj时研究ififjj1212例4.[HNOI2008]Toy15WC2016绵阳南山的结论：增的。下面有两个重要都是单调的，都是单调和该题则必须满足优，令比，如果时，可选决策计算igixigTxxyyTifjjjjjjjjjjjj*2,,)()()()(,211212211212斜率优化：再继续维护！列基础上加入新的决策时可以在之前维护的队并且在是最优的！！优。所以队首比优，比优，比来说，则对于所以可以删除。优，永远比时，有：，计算后面的是单调增的，则对于由于之间的斜率策如果队列中相邻两个决。。。，,11...,*2,....,,*2,,*2,*2*2,,*2,,*2,....,,*2,,*2,*2,...,,11322113221111111322121iififigTigTigTxxygigyxTfiigigyxTyxigTigTigTigifjjjjjjjjjjjjjiiiijjjjjjjjjjkkkkkkk证明：最优决策是队首元素即：的斜率都要大于使得这些相邻决策之间决策依次存储有价值的可选大策，使得队列中从小到可以删除其中的冗余决到i,时，所有可选决策是1结论1：计算例4.[HNOI2008]Toy16WC2016绵阳南山j1j2j3