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

《noip教程-动态规划的优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、第i天将所持的股票全部卖出所得的收入。时间复杂度是O(M3)。方法二设P[i]表示前i天能获得的最多股票数，则可列出状态转移方程：设Q[i]表示前i天能达到的最大收入，则可列出状态转移方程：时间复杂度是O(M2)。方法三分析：上述公式的含义是当0<=j

3、的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1)这组唱片中的歌曲必须按照它们创作的顺序排序；(2)包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。例2  RaucousRockers演唱组设n首歌曲按照创作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为：g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k

4、数目。状态转移方程为：当k≥long[i]，i≥1时：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}当k

5、,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

6、g[n,k]≤(m-1,t)}算法的时间复杂度为：O(n2)。优化方法2：利用决策的单调性例3：最长上升序列问题f(i)=max{f(j)+1}(1<=j

7、一个最大的f(j)反过来说，对于1<=j

8、r[j]bi，则用bi替换bj若在对尾，则直接插入显然该算法的时间复杂度为O(n*log(n))例4：最大子序和问题描述输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找

9、出一段连续的长度不超过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,