动态规划国家队论文资源-CSDN下载

动态规划

需积分: 31 199 浏览量 2011-05-20 09:18:43 上传评论收藏 443KB 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页未读，继续阅读

评论收藏

内容反馈

IAlgorithmer

粉丝: 0

动态规划国家队论文

noi国家队集训论文

NOI 国家集训队论文 1999-2009 2013-2017

IOI国家集训队论文集

国家集训队2019论文集_国家集训队2019论文集pdf_国家集训队2019_

国家队论文全集

国家集训队2018论文集_国家集训队2018论文集pdf_

2000年国家队论文集

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

国家集训队 论文 2006年

近年国家队论文.rar

国家集训队2016论文集1

ACM国家集训队论文集（第二卷）

1999-2009国家队论文集

国家队论文——线段树

2009年信息学奥林匹克中国国家国家集训队论文

国家集训队论文集.rar

2006-2009国家集训队论文

Qt上位机软件串口通讯，视频源码，免费下载

张玉生《C语言程序设计》双色版 C语言程序设计理论教材习题参考答案.pdf

代码随想录算法PDF.rar

qt-everywhere-src-5.12.12源码

Qt Qss三套样式文件 qss.zip

C++读取excel数据

第十二届蓝桥杯大赛模拟赛（第三期）.pdf

通俗易懂的校园导航系统

2021csp-j初赛试题及答案.docx

C++语言程序设计第五版郑莉

python多线程视频转为图片保存

《敏捷Java》：TDD引领的编程之道

最新资源

国家集训队论文 2006年