noip教程--动态规划的优化

动态规划的优化方法YALI朱全民动态规划优化的内涵动态规划算法的时间复杂度=阶段数*每个阶段状态转移的状态数*每次状态转移的时间或者:状态总数*每次状态转移的时间重点:减少每个阶段的状态数，也就是减少了状态总数优化方法1：改进状态的表示例1：理想收入问题理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。已知股票在第i天每股价格是V[i]元，1≤i≤M，求M天后的理想收入。方法一设F[i]表示在第i天收盘时能达到的最高收入，则有F[i]的递推关系式：1]0[1]0[]}[*][/][{max][)0(VFiVkVjFiFikj，，其中公式含义：在第i天收盘时能达到的最高的收入，是将第j天收盘后的收入，全部用于买入第k天的股票，再在第i天将所持的股票全部卖出所得的收入。时间复杂度是O(M3)。方法二设P[i]表示前i天能获得的最多股票数，则可列出状态转移方程：设Q[i]表示前i天能达到的最大收入，则可列出状态转移方程：]}[/][*][],1[{max][)0(iVjVjPiPiPij]}[*][/][],1[{max][)0(iVjVjQiQiQij时间复杂度是O(M2)。方法三分析：上述公式的含义是当0=ji时,求Q[i-1]和Q[j]*v[i]/v[j]的最大值对于0=ji，要求Q[i],实际上Q[1]…Q[i-1]都已经求出，因此我们只要搞一个变量保存Q[j]/V[j]的最大值即可，记为MaxQ.这样，公式可以写成]}[*][/][],1[{max][)0(iVjVjQiQiQij]}[*],1[{max][)0(iVMAXQiQiQij对每次求出的Q[i],都更新MaxQ,显然时间复杂度为O(M)[问题描述]现有n首由RaucousRockers演唱组录制的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1)这组唱片中的歌曲必须按照它们创作的顺序排序；(2)包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。例2RaucousRockers演唱组设n首歌曲按照创作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为：g[i,j,k]，(0≤i≤n，0≤j≤m，0≤kt),表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目。状态转移方程为：当k≥long[i]，i≥1时：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}当klong[i]，i≥1时：g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}规划的边界条件为：当0≤j≤m，0≤kt时：g[0,j,k]=0;问题的最优解为：g[n,m,0]。算法的时间复杂度为：O(n*m*t)。改进的状态表示描述为：g[i,j]=(a,b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱片另加b分钟。状态转移方程为：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的计算方法为：当b+long[i]≤t时：a’=a;b’=b+long[i];当b+long[i]＞t时：a’=a+1;b’=long[i];规划的边界条件：当0≤i≤n时，g[i,0]=(0,0)题目所求的最大值是：answer=max{k|g[n,k]≤(m-1,t)}算法的时间复杂度为：O(n2)。优化方法2：利用决策的单调性例3：最长上升序列问题f(i)=max{f(j)+1}(1=ji=n,bjbi)上式含义为：对于所有的1=ji，bjbi,必须找一个最大的f(j)反过来说，对于1=ji，必须找到一个最大的f(j),满足bjbi。分析对方程进行一下改进：对于ji,f[i]=max{f(j)+1},其中，min{j|r[j]a[i]}r[j]为所有等于f[j]时a[j]的最小值。因此，我们可以搞一个队列维护f(j)的上升序列。对于当前的i，利用二分查找在队列查找到满足条件bjbi的f(j)用bi去替换与f(i)相等的bj–若bj=bi,则舍弃bi–若bjbi，则用bi替换bj–若在对尾，则直接插入显然该算法的时间复杂度为O(n*log(n))例4：最大子序和问题描述输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。最大子序和输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段长度不超过m的连续的子序列，使得这个序列的和最大。例如：序列1，-3，5，1，-2，3当M=2或3时,S=5+1=6当M=4时,S=5+1-2+3=7数据范围:50%的数据N,M=1000100%的数据N,M=20000一个简化的问题[序列的最大连续和]输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段连续的子序列，使得这个序列的和最大。和原问题相比没有M这个序列长度的限制！设F(i)表示以第i个数结尾的最大连续和以第i个数结尾的最大连续和序列，可能存在两种选择：情形一：只包含Ai情形二：包含Ai和以Ai-1结尾的最大连续和序列状态转移方程如下：F(i)=max{Ai,F(i-1)+Ai}边界：F(1)=A1，Ans=max{F(i)|1=i=n}该算法的时间复杂度为O(n)分析算法一——枚举设F(i)为以Ai结尾长度不超过M的最大子序和ikijjmkAiF1}..1|max{)(对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)简化方程ikijjmkAiF1}..1|max{)(i1jjA)i(S令}..1|)(min{)(}..1|)()(max{mkkiSiSmkkiSiS用一个二叉堆来维护S(i-k)，每次求F(i)之前的操作如下：}..1|)(min{)()(mkkiSiSiF算法二——堆求F(i-1)时，求min{S(i-m-1),……,S(i-2)}求F(i)时，求min{S(i-m),……,S(i-1)}☆在堆中删除元素S(i-m-1)，插入元素S(i-1).复杂度O(2log2n)☆从堆中取出当前最小值.复杂度O(1)所以计算的总复杂度为O(nlog2n)队列优化在算法二中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-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)从队尾删除掉（此时队列的尾部形成了一个类似栈的结构）队列优化同理，若队列中两个元素S(i)和S(j)，若ij且S(i)=S(j)，则我们可以删掉S(i)（因为S(i)永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，即：S1S2S3……Sk算法三我们来整理在求F(i)的时候，用队列维护S(i-k)所需要的操作：☆若当前队首元素S(x)，有xi-m，则S(x)出队；直到队首元素S(x)有x=i-m为止。☆若当前队尾元素S(k)=S(i-1)，则S(k)出队；直到S(k)S(i-1)为止。☆在队尾插入S(i-1)☆取出队列中的最小值，即队首元素。算法三由于对于求每个F(i)的时候，进队和出队的元素不止一个。但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是O(n)。综上所述，该算法的总复杂度是O(n)方法3：根据最优解的性质减少决策例5：石子合并问题]},[],1[],[{],[max1jitjkmkimjimjki规划的边界条件为：m[i,i]=0令s[i,j]=k，表示合并的最优断开位置。算法的时间复杂度为O(n3)。猜想合并第i堆到第j堆石子的最优断开位置s[i,j]要么等于i，要么等于j-1，也就是说最优合并方案只可能是：{(i)(i+1…j)}或{(i…j-1)(j)}证明：设合并第i堆到第j堆石子的最优断开位置s[i,j]=p，且ipj-1。情况1：t[i,p]≤t[p+1,j]由于ip，所以可以设q=s[i,p]。于是最优合并方案为：{[(i…q)(q+1...p)](p+1…j)}，它的得分，F1=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[i,p]我们可以构造如下的合并方案：{(i…q)[(q+1...p)(p+1…j)]}，它的得分，F2=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[q+1,j]由于qp，所以t[i,p]≤t[p+1,j]t[q+1,j]，所以F1F2。这与合并第i堆到第j堆石子的最优断开位置s[i,j]=p矛盾情况2：t[i,p]t[p+1,j]与情况1是对称的。方法4:利用贪心思想减少状态总数例6：快餐问题Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出:每天套餐的最大产量。分析设p[i,j,k]表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。用r[i,j,k]表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。状态转移方程如下：p[i,j,k]=Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}约束条件：(0=j1=j=100,0=k1=k=100,&&(j-j1)*p1+(k-k1)*p2=T[i])r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的时间复杂度为O(N*1004),优化在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计算，即min｛100divA，100divB，100divc｝），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。贪心优化显然，对每条流水线，我们没有必要将对每个时