noip教程-动态规划的优化

1、动态规划的优化方法YALI 朱全民1动态规划优化的内涵动态规划算法的时间复杂度= 阶段数*每个阶段状态转移的状态数 *每次状态转移的时间 或者:状态总数*每次状态转移的时间重点:减少每个阶段的状态数，也就是减少了状态总数2优化方法1：改进状态的表示例1：理想收入问题理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。已知股票在第i天每股价格是Vi元，1iM，求M天后的理想收入。3方法一设Fi表示在第i天收盘时能达到的最高收入，则有Fi的递推关系式：公式含义：在第i天收盘时能达到的最高的收入，是将第j天收盘后的收入，全部用于买入第k天的股票，再在第i天

2、将所持的股票全部卖出所得的收入。时间复杂度是O(M3)。 4方法二设Pi表示前i天能获得的最多股票数，则可列出状态转移方程：设Qi表示前i天能达到的最大收入，则可列出状态转移方程： 时间复杂度是O(M2)。5方法三分析：上述公式的含义是当0=ji 时,求Qi-1和Qj*vi/vj的最大值 对于0=ji，要求Qi,实际上Q1Qi-1都已经求出，因此我们只要搞一个变量保存Qj/Vj 的最大值即可，记为MaxQ.这样，公式可以写成对每次求出的Qi,都更新MaxQ,显然时间复杂度为O(M)6 问题描述 现有n首由Raucous Rockers 演唱组录制的歌曲，计划从中选择一些歌曲来发行m张唱片，每张

3、唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择： (1) 这组唱片中的歌曲必须按照它们创作的顺序排序； (2) 包含歌曲的总数尽可能多。 输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。例2 Raucous Rockers 演唱组7 设n首歌曲按照创作顺序排序后的长度为long1.n，则动态规划的状态表示描述为： gi, j, k，(0in，0jm，0kt), 表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目。状态转移方程为：当klongi，i1时：gi

4、, j, k=maxgi-1,j,k-longi+1，gi-1,j,k当klongi，i1时：gi, j, k=maxgi-1,j-1,t-longi+1，gi-1,j,k规划的边界条件为：当0jm， 0kt时：g0,j,k=0;问题的最优解为：gn,m,0。算法的时间复杂度为：O(n*m*t)。8改进的状态表示描述为： gi,j=(a, b)，0in，0ji，0am，0bt，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱片另加b分钟。状态转移方程为：gi, j=mingi-1,j，gi-1,j-1+longi 其中(a, b)+longi=(a, b)的计算方法为：当b+longi

5、t时： a=a; b=b+longi;当b+longi t时： a=a+1; b=longi;规划的边界条件：当0in时，gi,0=(0,0) 题目所求的最大值是：answer=maxk| gn, k(m-1,t) 算法的时间复杂度为：O(n2)。9优化方法2：利用决策的单调性例3：最长上升序列问题 f(i)=maxf(j)+1 (1=ji=n, bjbi)上式含义为：对于所有的1=ji，bjbi,必须找一个最大的f(j)反过来说，对于1=ji，必须找到一个最大的f(j),满足bjbi。10分析对方程进行一下改进：对于 ji,fi = maxf(j)+1, 其中，minj | r jairj为

6、所有等于fj时aj的最小值。因此，我们可以搞一个队列维护f(j)的上升序列。对于当前的i，利用二分查找在队列查找到满足条件bjbi的f(j)用bi去替换与f(i)相等的bj若bjbi，则用bi替换bj若在对尾，则直接插入显然该算法的时间复杂度为O(n*log(n)11 例4：最大子序和问题描述 输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。12最大子序和输入一个长度为的整数序列（A1,A2,An），从中找出一段长度不超过m的连续的子序列，使得这个序列的和最大。例如：序列 1， -3， 5， 1， -2， 3当M=2或3时,S=5+1

7、=6当M=4时,S=5+1-2+3=7数据范围: 50%的数据N,M=1000 100%的数据N,M=2000013一个简化的问题序列的最大连续和 输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的子序列，使得这个序列的和最大。 和原问题相比没有M这个序列长度的限制！14设 F(i)表示以第i个数结尾的最大连续和 以第i个数结尾的最大连续和序列，可能存在两种选择： 情形一：只包含Ai 情形二：包含Ai和以Ai-1结尾的最大连续和序列状态转移方程如下： F(i)=maxAi , F(i-1)+Ai边界：F(1)=A1，Ans=maxF(i)|1=i=n该算法的时间复杂度为O(n)分

8、析15算法一枚举设 F(i)为以Ai结尾长度不超过M的最大子序和 对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)16简化方程17 用一个二叉堆来维护S(i-k)，每次求F(i)之前的操作如下：算法二堆求F(i-1)时，求minS(i-m-1), ,S(i-2)求F(i)时， 求minS(i-m),S(i-1)在堆中删除元素S(i-m-1)，插入元素S(i-1).复杂度O(2log2n)从堆中取出当前最小值.复杂度O(1) 所以计算的总复杂度为O(nlog2n)18队列优化 在算法二中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i

9、-m-1)，在队尾添加S(i-1) 。但是取最小值操作还是需要O(n)时间复杂度的扫描。 考察在添加S(i-1)的时候，设现在队尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出队。若此时S(i-1)=S(k)，则S(k)这个决策永远不会在以后用到，可以将S(k)从队尾删除掉（此时队列的尾部形成了一个类似栈的结构）19队列优化 同理，若队列中两个元素S(i)和S(j)，若i=S(j)，则我们可以删掉S(i)（因为S(i)永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，即：S1S2S3Sk20算法三 我们来整理在求F(i)的时候，用队列维护S(i-k)所需要的操作

10、： 若当前队首元素S(x)，有x=i-m为止。 若当前队尾元素S(k)=S(i-1)，则S(k)出队；直到S(k)S(i-1)为止。 在队尾插入S(i-1) 取出队列中的最小值，即队首元素。21算法三 由于对于求每个F(i)的时候，进队和出队的元素不止一个。 但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是O(n)。 综上所述，该算法的总复杂度是O(n)22方法3：根据最优解的性质减少决策例5：石子合并问题 规划的边界条件为：mi,i=0 令si,j=k，表示

11、合并的最优断开位置。 算法的时间复杂度为O(n3)。23猜想合并第i堆到第j堆石子的最优断开位置si,j要么等于i，要么等于j-1，也就是说最优合并方案只可能是： (i) (i+1 j) 或 (i j-1) (j) 24证明：设合并第i堆到第j堆石子的最优断开位置 si,j=p，且ipj-1。情况1：ti, ptp+1,j 由于ip，所以可以设q=si,p。于是最优合并方案为： (iq) (q+1.p) (p+1j) ，它的得分， F1=mi, q+mq+1,p+mp+1,j+ti, j+ti, p我们可以构造如下的合并方案： (iq) (q+1.p) (p+1j) ，它的得分， F2 = m

12、i, q+mq+1,p+mp+1,j+ti, j+tq+1,j由于qp，所以ti, ptp+1,jtq+1,j，所以F1tp+1,j 与情况1是对称的。25方法4:利用贪心思想减少状态总数例6：快餐问题Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请

13、你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出:每天套餐的最大产量。 26分析设pi,j,k表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。用ri,j,k表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。状态

14、转移方程如下： pi,j,k = Maxpi-1,j1,k1+ri,j-j1,k-k1约束条件： ( 0=j1=j=100,0=k1=k=100, & (j-j1)*p1+(k-k1)*p2=Ti) ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2) div p3 ;此算法的时间复杂度为O(N*1004), 27优化在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计算，即min100 div A，100 div B，100 div c），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，

15、否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。28贪心优化显然，对每条流水线，我们没有必要将对每个时刻都进行动态规划，可以拿出大部分时间进行成套生产，剩下一些时间进行动态规划这样，显然可以极大的减少动态规划的状态总数，从而节约动态规划的计算时间。29例7：Hotel 有N个男人，M个女人，其中有C对夫妇要住房。现在有P个房子。每个房子有个费用Ci和床位Bi。住房有以下要求:1.每个房子住

16、的人数不能超过Bi2.一个房间住了夫妇，不能再住其他人。3.不考虑夫妇情况下：一个房间住了男人后，不能再住女人。对女人也是一样。问最少的费用。(n500,m500,P500,Bisize,lsize) ，那么肯定无论如何Ci/Bi最小的那些房间肯定会被选到。于是我们可以贪心在ksize,lsize的时候，给他们安排Ci/Bi最小的房间。然后再进行动态规划。由于Bi=5.所以size=20就够了。这样时间复杂度就很低了。33方法4：利用恰当的数据结构存储状态，减少状态查找时间例6、LOSTCITY现给出一张单词表、特定的语法规则和一篇文章：文章和单词表中只含26个小写英文字母az。单词表中的单词

17、只有名词，动词和辅词这三种词性，且相同词性的单词互不相同。单词的个数不超过1000，单词的长度均不超过20。语法规则可简述为：名词短语：任意个辅词前缀接上一个名词；动词短语：任意个辅词前缀接上一个动词；句子：以名词短语开头，名词短语与动词短语相间连接而成。文章的长度不超过5k。且已知文章是由有限个句子组成的，句子只包含有限个单词。编程将这篇文章划分成最少的句子，在此前提之下，要求划分出的单词数最少。34我们分别用v,u,a表示动词，名词和辅词，给出的文章用L1.M表示，则状态表示描述为：F(v,i)：表示将L的前i个字符划分为以动词结尾（当iM时，可带任意个辅词后缀）的最优分解方案下划分的句子

18、数与单词数；F(u,i)：表示将L的前i个字符划分为以名词结尾（当iM时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数。状态转移方程为：F(v,i)=min F(u,j)+(0,1)， L(j+1.i)为动词； F(v,j)+(0,1)， L(j+1.i)为辅词，iM；F(u,i)=min F(u,j)+(1,1), L(j+1.i)为名词； F(v,j)+(0,1), L(j+1.i)为名词； F(u,j)+(0,1), L(j+1.i)为辅词，iM；边界条件：F(v,0)=(1,0)； F(u,0)=(, )；问题的解为：min F(v,M), F(u,M) ；35采用不同的方

19、法查找字符串的比较： 设单词表的规模为N（N的最大值为1000） 设文章的长度为M（M的最大值为 5000）36方法5：利用四边形不等式的性质降维例8：邮局按照递增顺序给出一条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局的距离总和最小。试编程计算最小距离和，以及邮局建立方案。 37分析将n个村庄按坐标递增依次编号为1.n，第i个邮局的坐标为di，wi,j表示在di,j之间建立一个邮局的最小距离和。设mi,j表示在前j个村庄建立i个邮局的最小距离和。38分析可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k 同时，令si,j=k，记录使用前i-1个邮局的村庄数，便于在算出最小距离和之后构造最优建立方案。上述算法中wi,j可通过O(n)时间的预处理，在O(1)的时间内算出，所以，该算法的状态总数为O(n*p)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，该算法总的时间复杂度为O(p*n2)。39猜想 W满足四边形不等式，即证明：设y=(i+j)/2,z=(i+j)/2,下面分为两种情形，z