【免费】算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》1资源-CSDN文库

需积分: 0 47 浏览量 2022-08-04 11:57:40 上传评论收藏 444KB PDF 举报

资源详情

资源评论

资源推荐

IOI2004 国家集训队论文朱晨光

第 1 页共 22 页

优化，再优化！

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

安徽省芜湖市第一中学朱晨光

Ø 关键字........................................................................................2

Ø 摘要............................................................................................2

Ø 正文............................................................................................2

n 引言 ......................................................................................2

n 问题 ......................................................................................2

n 分析 ......................................................................................3

u 算法一.............................................................................3

u 算法二.............................................................................4

u 算法三.............................................................................4

u 算法四.............................................................................6

u 小结.................................................................................7

u 算法五.............................................................................7

Ø 总结..........................................................................................10

Ø 结束语.......................................................................................11

IOI2004 国家集训队论文朱晨光

第 2 页共 22 页

关键字

优化动态规划模型

摘要

本文就 Ural 1223 《鹰蛋》这道题目介绍了五种性能各异的算法，并在此基础上

总结了优化动态规划算法的本质思想及其一般方法。全文可以分为四个部分。

第一部分引言，阐明优化动态规划算法的重要性；

第二部分给出本文讨论的题目；

第三部分详细讨论这道题目五种不同的动态规划算法，并阐述其中的优化思想；

第四部分总结全文，再次说明对于动态规划进行优化的重要性，并分析优化动态

规划的本质思想与一般方法。

正文

引言

在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。它以其高

效性受到大家的青睐。然而，动态规划算法有时也会遇到时间复杂度过高的问题。

因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。

优化动态规划的方法有许多，例如四边形不等式、斜率优化等。但是这些方

法只能对某些特定的动态规划算法进行优化，尚不具有普遍的意义。本文将就《鹰

蛋》这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想与一般方

法。

问题

有一堆共 M 个鹰蛋，一位教授想研究这些鹰蛋的坚硬度 E。他是通过不断

从一幢 N 层的楼上向下扔鹰蛋来确定 E 的。当鹰蛋从第 E 层楼及以下楼层落下

时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔

碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定 E，这显然是一个失败的实

验。教授希望实验是成功的。

例如：若鹰蛋从第 1 层楼落下即摔碎，E=0；若鹰蛋从第 N 层楼落下仍未碎，

E=N。

这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数 M 与楼层数 N。

要求最坏情况下确定 E 所需要的最少次数。

IOI2004 国家集训队论文朱晨光

第 4 页共 22 页

算法二

这个算法的时间复杂度太高，有没有可以优化的余地呢？答案是肯定的。首

先，这题很类似于二分查找，即每次根据扔鹰蛋所得信息来决定下一步操作的区

间，只不过对鹰蛋碎的次数有限制罢了。假设我们对于鹰蛋的个数不加限制，那

么根据判定树的理论

，叶子结点个数共有(n+1)个，（E 的取值只可能是 0,1,2,

…

共（n+1）种情况），则树的高度至少为





)1(log

+n +1,即比较次数在最坏情况下

需要





)1(log

+n 次。而我们又知道，在 n 个排好序的数里进行二分查找最坏情

况下需要比较





)1(log

+n 次（在这个问题中，若未查找到可视为 E=0）。这两点

便决定了





)1(log

+n 是下限而且是可以达到的下限。换句话说，对于一个确定

的 n，任意 M 所得到的结果均不会小于





)1(log

+n 。一旦 M>=





)1(log

+n ,该

题就成了求二分查找在最坏情况下的比较次数，可以直接输出





)1(log

+n 。因

此时间复杂度立即降为 O(N

log

N).

由此可见，对于动态规划的优化是十分必要的。算法二仅通过考察问题自身

的性质便成功地减少了状态总数，从而降低了算法一的时间复杂度，大大提高了

算法效率。

算法三

然而优化还远未结束。经实践证明，M 的大小已经不能再加限制了，因此

我们不妨从动态规划方程本身入手，探寻新的优化手段。

在实际操作中，我们发现 f(i,j)>=f(i,j-1) (j>=1)总是成立的。那么是否可以对

该性质进行证明呢？是的。这里用数学归纳法加以证明。

当 i=1 时，由于 f(1,j)=j (j>=0),显然有 f(i,j)>=f(i,j-1)(j>=1)成立。

当 i>=2 时

,f(i,0)=0,f(i,1)=max{f(i-1,0),f(i,0)}+1=1,即当 j=1 时，f(i,j)>=f(i,j-1)

现在假设当 j=k-1 时,f(i,j)>=-f(i,j-1)成立(k>1) ,则当 j=k 时,

f(i,j)=f(i,k)=min{max{f(i-1,w-1),f(i,k-w)}+1|1<=w<=k}

f(i,j-1)=f(i,k-1)=min{max{f(i-1,w-1),f(i,k-1-w)}+1|1<=w<=k-1}

当 1<=w<=k-1 时,∵k-1-w<k-w<=k-1,根据归纳假设，有 f(i,k-w)>=f(i,k-1-w),

∴max{f(i-1,w-1),f(i,k-w)}+1>=max{f(i-1,w-1),f(i,k-1-w)}+1

有关判定树的理论详情请见参考文献[1]第 292~293 页。

2 这里，我们按照 i依次增大的顺序进行证明，即先证明 i =2的情况，再证明 i=3的情况，…… ,

依此类推。

剩余42页未读，继续阅读

评论收藏

内容反馈

天眼妹

粉丝: 21
资源: 333

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

评论0

最新资源

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

评论0

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

算法合集之从鹰蛋一题浅析对动态规划算法的优化PPT学习教案.pptx

acm国家集训队2004年论文合集

IOI国家集训队2004论文集

IOI国家集训队论文集1999-2019

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

2024最新：Hvv中常见的面试问题

全面的安全基线核查清单

OpenVAS离线资源

CISP、NISP二级、CISE题库最新版（2024年1月更新）

软件工程导论(第六版)课后习题答案1

STM32F103C8T6核心板-电路原理图1.PDF

goby红队&社区版-win-64-2.4.7

hackbar2.1.3-master安装包

2023年最全最精简wifi密码字典(2.6G)

LiqunKit-1.6.2

UN R155 信息安全法规 中英文版

密码编码学与网络安全-原理与实践 第八版 习题答案1-10章 英文版

Kali安装burpsuite专业版

14.视觉SLAM十四讲(高翔第二版)1

jssecacerts

2021年11月更新的哥斯拉4.0.1 免费

最新资源

UN R155 信息安全法规中英文版

密码编码学与网络安全-原理与实践第八版习题答案1-10章英文版