《noip教程--动态规划的优化》由会员分享，可在线阅读，更多相关《noip教程--动态规划的优化（43页珍藏版）》请在金锄头文库上搜索。
1、动态规划的优化方法YALI 朱全民动态规划优化的内涵u动态规划算法的时间复杂度=阶段数*每个阶段状态转移的状态数*每次状态转移的时间或者:状态总数*每次状态转移的时间u重点:减少每个阶段的状态数，也就是减少 了状态总数优化方法1：改进状态的表示u例1：理想收入问题u理想收入是指在股票交易中，以1元为本金 可能获得的最高收入，并且在理想收入中 允许有非整数股票买卖。u已知股票在第i天每股价格是Vi元， 1iM，求M天后的理想收入。方法一u设Fi表示在第i天收盘时能达到的最高收 入，则有Fi的递推关系式：公式含义：在第i天收盘时能达到的最高的收 入，是将第j天收盘后的收入，全部用于买入 第k天的股
2、票，再在第i天将所持的股票全部 卖出所得的收入。 时间复杂度是O(M3)。 方法二u设Pi表示前i天能获得的最多股票数，则 可列出状态转移方程：u设Qi表示前i天能达到的最大收入，则可 列出状态转移方程： 时间复杂度是O(M2)。方法三u分析：上述公式的含义是当0bi，则则用bi替换换bj 若在对对尾，则则直接插入u显显然该该算法的时间时间 复杂杂度为为O(n*log(n)例4：最大子序和问题描述输入一个长度为的整数序 列（A1,A2,An），从中找出 一段连续的长度不超过M的子序 列，使得这个序列的和最大。最大子序和输入一个长度为的整数序列（A1,A2,An），从中 找出一段长度不超过m的连
3、续的子序列，使得这个序列的和 最大。例如：序列 1， -3， 5， 1， -2， 3当M=2或3时,S=5+1=6当M=4时,S=5+1-2+3=7数据范围:50%的数据N,M=S(j)，则我们可以删掉S(i)（ 因为S(i)永远不会被用到）。此时的队列 中的元素构成了一个单调递增的序列，即 ：S1=i-m为 止。若当前队尾元素S(k)=S(i-1)，则S(k) 出队；直到S(k)tp+1,j 与情况1是对称的。方法4:利用贪心思想减少状态总数u例6：快餐问题uPeter最近在R市开了一家快餐店，为了招揽顾客，该快餐店 准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料 组成。价格便宜。为
4、了提高产量，Peter从著名的麦当劳公司 引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮 料，由于每条生产线每天所能提供的生产时间是有限的、不同 的，而汉堡，薯条和饮料的单位生产时间又不同。这使得 Peter很为难，不知道如何安排生产才能使一天中生产的套餐 产量最大。请你编一程序，计算一天中套餐的最大生产量。为 简单起见，假设汉堡、薯条和饮料的日产量不超过100个。u输入:第一行为三个不超过100的正整数A、B、C中间以一个 空格分开。第二行为3个不超过100的正整数p1,p2,p3分别 为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。 第三行为N(0size,lsize) ，那
5、么肯定u无论如何Ci/Bi最小的那些房间肯定会被选到。u于是我们可以贪心在ksize,lsize的时候，给 他们安排Ci/Bi最小的房间。u然后再进行动态规划。u由于BiM时，可带任意个辅 词后缀）的最优分解方案下划分的句子数与单词数；F(u,i)：表示将L的前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)为辅词，iy，下面仅讨论zy，zy的情况是类似的。u由izyj有： 证明u用数学归纳法证明函数m也满足四边形不等式。对四边形 不等式中
6、“长度”l=j-i进行归纳：u当i=i或j=j时，不等式显然成立。由此可知，当l1时 ，函数m满足四边形不等式。u下面分两种情形进行归纳证明： 情形1：ij。下面只讨论kj，kj的情况 是类似的。u情形2：iy。u情形2.1，当zyjj时：情形情形2.22.2，当，当i-1i-1yzji-1i-1yzj时：时：u令si,j=k，(ij)，最后，我们证明决策si,j满足单调性。u令mki,j=mi-1,k+wk+1,j；u我们先来证明si-1,jsi,j，只要证明对于所有ikkj且 mki-1,jmki-1,j，有：mki,jmki,j。u类似地，我们可以证明一个更强的不等式mki-1,j-mk
7、i-1,jmki,j-mki,jmki-1,j+mki,jmki,j+mki-1,ju利用递推定义式展开整理的：mi-2,k+mi-1,kmi- 1,k+mi-2,k，这就是i-2i-1kk时m的四边形不等式 。u我们再来证明si,jsi,j+1，设kkj，则我们只需证明一个更强的不等式： mki,j-mki,jmki,j+1-mki,j+1u也就是mki,j+mki,j+1mki,j+1+mki,ju利用递推定义式展开整理的： wk+1,j+wk+1,j+1wk+1,j+1+wk+1,j，这就是k+1k+1jj+1时w的四边形不等式。u综上所述，该问题的决策si,j具有单调性，因此u优化后的算法时间复杂度为O(n*p)。
