算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》

《算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2004国家集训队论文朱晨光优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化安徽省芜湖市第一中学朱晨光目录Ø关键字........................................................................................2Ø摘要............................................................................................2Ø正文...............................

2、.............................................................2n引言......................................................................................2n问题......................................................................................2n分析......................................

3、................................................3u算法一.............................................................................3u算法二.............................................................................4u算法三..................................................................

4、...........4u算法四.............................................................................6u小结.................................................................................7u算法五.............................................................................7Ø总结...................

5、.......................................................................10Ø结束语.......................................................................................11第1页共22页IOI2004国家集训队论文朱晨光关键字优化动态规划模型摘要本文就Ural1223《鹰蛋》这道题目介绍了五种性能各异的算法，并在此基础上总结了优化动态规划算法的本质思想及其一般方法。全文可以分为四个部分。第一部分引言，阐

6、明优化动态规划算法的重要性；第二部分给出本文讨论的题目；第三部分详细讨论这道题目五种不同的动态规划算法，并阐述其中的优化思想；第四部分总结全文，再次说明对于动态规划进行优化的重要性，并分析优化动态规划的本质思想与一般方法。正文引言在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。它以其高效性受到大家的青睐。然而，动态规划算法有时也会遇到时间复杂度过高的问题。因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。优化动态规划的方法有许多，例如四边形不等式、斜率优化等。但是这些方法只能对某些特定的动态规划算法进行优化，尚不具有普遍的意义。本文将

7、就《鹰蛋》这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想与一般方法。问题有一堆共M个鹰蛋，一位教授想研究这些鹰蛋的坚硬度E。他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。当鹰蛋从第E层楼及以下楼层落下时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实验。教授希望实验是成功的。例如：若鹰蛋从第1层楼落下即摔碎，E=0；若鹰蛋从第N层楼落下仍未碎，E=N。这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数M与楼层数N。要求最坏情况下确定E所需要的最少次数。第

8、2页共22页IOI2004国家集训队论