预览加载中，请您耐心等待几秒...

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

预览
1/10
2/10
3/10
4/10
5/10
6/10
7/10
8/10
9/10
10/10

亲，该文档总共43页，到这已经超出免费预览范围，如果喜欢就直接下载吧～

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

IOI2004国家集训队论文朱晨光 优化，再优化！ ——从《鹰蛋》一题浅析对动态规划算法的优化 安徽省芜湖市第一中学朱晨光 目录 Ø关键字........................................................................................2 Ø摘要............................................................................................2 Ø正文............................................................................................2 n引言......................................................................................2 n问题......................................................................................2 n分析......................................................................................3 u算法一.............................................................................3 u算法二.............................................................................4 u算法三.............................................................................4 u算法四.............................................................................6 u小结.................................................................................7 u算法五.............................................................................7 Ø总结..........................................................................................10 Ø结束语.......................................................................................11 IOI2004国家集训队论文朱晨光 关键字 优化动态规划模型 摘要 本文就Ural1223《鹰蛋》这道题目介绍了五种性能各异的算法，并在此基础上 总结了优化动态规划算法的本质思想及其一般方法。全文可以分为四个部分。 第一部分引言，阐明优化动态规划算法的重要性； 第二部分给出本文讨论的题目； 第三部分详细讨论这道题目五种不同的动态规划算法，并阐述其中的优化思想； 第四部分总结全文，再次说明对于动态规划进行优化的重要性，并分析优化动态 规划的本质思想与一般方法。 正文 引言 在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。它以其高 效性受到大家的青睐。然而，动态规划算法有时也会遇到时间复杂度过高的问题。 因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。 优化动态规划的方法有许多，例如四边形不等式、斜率优化等。但是这些方 法只能对某些特定的动态规划算法进行优化，尚不具有普遍的意义。本文将就《鹰 蛋》这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想与一般方 法。 问题 有一堆共M个鹰蛋，一位教授想研究这些鹰蛋的坚硬度E。他是通过不断 从一幢N层的楼上向下扔鹰蛋来确定E的。当鹰蛋从第E层楼及以下楼层落下 时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔 碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实 验。教授希望实验是成功的。 例如：若鹰蛋从第1层楼落下即摔碎，E=0；若鹰蛋从第N层楼落下