资源描述：
《国家集训队2004论文集 朱晨光》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化安徽省芜湖市第一中学朱晨光引言在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。它以其高效性受到大家的青睐。然而，动态规划算法有时也会遇到时间复杂度过高的问题。因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。本文将就《鹰蛋》这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想与一般方法。问题当鹰蛋从第E层楼及以下楼层落下时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。有一堆共M个鹰蛋，一位教授想研究这些鹰蛋的坚硬度E。他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。如果鹰蛋未摔碎，还可以继续使
2、用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实验。教授希望实验是成功的。问题例如：若鹰蛋从第1层楼落下即摔碎，E=0；若鹰蛋从第N层楼落下仍未碎，E=N。这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数M与楼层数N(M,N<=1000),求最坏情况下确定E所需要的最少次数。样例：M=1，N=10ANS=10（解释：只能将这个鹰蛋从下往上依次摔）算法一由于是求最优值，我们自然想到了使用动态规划！算法一状态定义：f(i,j):用i个蛋在j层楼上最坏情况下确定E所需要的最少次数。状态转移：i个鹰蛋(j-w)层(i-1)个鹰蛋(w-1)层i个鹰蛋j层f(i-1,w-1)次f(i,j-w)次算
3、法一状态定义：f(i,j):用i个蛋在j层楼上最坏情况下确定E所需要的最少次数。状态转移：f(i,j)=min{max{f(i-1,w-1),f(i,j-w)}+1
4、1<=w<=j}算法一显然，这个算法的时间复杂度为O(N3)太高了！如何才能降低它的时间复杂度呢？算法二经过观察，我们发现这题很类似于二分查找，只不过是对鹰蛋的个数有限制。若是对鹰蛋的个数没有限制呢？这题就变成求二分查找在最坏情况下的比较次数！答案即为算法二因此，当M>=时，直接输出即可.算法的时间复杂度立即降为O(N2log2N)算法二这里，我们是通过减少状态总数而得到了优化的空间，从而大大提高了算法效率。这也是优化动态规划算法
5、的一种常用方法。然而优化还远未结束！算法三经观察发现，动态规划函数f(i,j)具有如下单调性：f(i,j)>=f(i,j-1)(j>=1)这条性质可以用数学归纳法进行证明，这里就从略了。那么，f(i,j)的单调性有什么作用呢？算法三（如图，令①为f(i-1,w-1)的图象，②为f(i,j-w)的图象,③即为max{f(i-1,w-1),f(i,j-w)}+1的图象）算法三这样，我们就成功地将状态转移的时间复杂度降为O(log2N)，算法的时间复杂度也随之降为O(N(log2N)2).在对算法三进行研究之后，我们会萌生一个想法：既然现在f(i,j)都需要求出，要想找到更高效的算法就只能从状态转移
6、入手，因为这一步是O(log2N)，仍然不够理想。因此，算法四将以状态转移为切入点，进一步探究优化的空间。算法四根据这个不等式，我们可以得到如下推理：若存在一个决策w使得f(i,j)=f(i,j-1)，则f(i,j)=f(i,j-1)若所有决策w均不能使f(i,j)=f(i,j-1)，则f(i,j)=f(i,j-1)+1通过进一步挖掘状态转移方程，我们得到如下不等式：f(i,j-1)<=f(i,j)<=f(i,j-1)+1(j>=1)算法四这里，我们设一指针p，并使p时刻满足：f(i,p)=f(i,j-1)-1且f(i,p+1)=f(i,j-1)由状态转移方程可知，决策时f(i,p)所对应的函
7、数值是f(i-1,j-p-1).下面，我们将证明只需通过判断f(i,p)与f(i-1,j-p-1)的大小关系便可以决定f(i,j)的取值。算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1s大于等于j-1(s=j-p-1)算法四f(i-1)f(i)jjp+1p
8、sj-1算法四f(i-1)f(i)jjpp+1sf(i,j)=f(i,j-1)j-1算法四f(i-1)f(i)jjpp+1s小于f(i-1,s)>f(i,p)=f(i,j-1)-1j-1情况一（p’f(i,j-1)大于等于大于大于等于j-1情况二（p’=p)f(i-1)f(i)jjp+1p’s’j-1
