《动态规划初步》PPT课件

《《动态规划初步》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划初步JSOI2007夏令营B层次（泰州）常州市第一中学林厚从问题：城市交通有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少？输入格式：先输入一个n，表示城市数，n<100。下面的n行，是一个n*n的邻接矩阵map[1..n,1..n]。map[i,j]=0，表示城市i和城市j之间没有路相连，否则为两者之间的距离。输出格式：一个数，表示从城市1走到城市n的最短距离。输入数据保证可以从城市1走

2、到城市n。动态规划的引入常州市第一中学林厚从输入样例：110530000000050016300000300080400000100000560006800005000030000000800040000003000055000003000600000040000083000300000003430动态规划的引入常州市第一中学林厚从设一个数组dis[1..n]，dis[i]表示城市1到城市i的最短距离。题目就是要求dis[n]。根据题目的限制条件：只能从编号小的城市到编号大的城市。显然，我们可以从城市1、城市2、……、城市n-1到

3、城市n，前提是城市i与城市n之间有路，其中i=1，2，3，……，n-1。所以，dis[n]就应该取dis[i]+map[i，n]中的最小值，且要求map[i，n]<>0，i=1，2，3，……，n-1。也就是说要求dis[n]，就必须先求出dis[1]~dis[n-1]，类似于递推算法中的“倒推法”，那么如何求dis[n-1]呢？dis[n-1]=min{dis[i]+map[i，n-1]}且要求map[i，n-1]<>0，i

4、is[i]=min{dis[j]+map[j，i]}要满足：map[j，i]<>0，j=1..i-1这是一个类似于递归的公式，意思为：要求dis[n]就要先求dis[n-1]~dis[1]，要求dis[n-1]就要先求dis[n-2]~dis[1]，而要求dis[i]，就要先求dis[i-1]~dis[1]，……，而dis[1]=0。在具体计算的时候，只要从dis[1]开始“顺推”下去，依次求出dis[2]、dis[3]、……、dis[n-1]、dis[n]即可。城市交通分析常州市第一中学林厚从……dis[1]:=0;fori:=

5、2tondobeginmin:=maxint;{用打擂台的方法求出最小值}forj:=1toi-1doifmap[j,i]<>0thenifdis[j]+map[j,i]

6、划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。动态规划运用于信息学竞赛是在90年代初期，它以独特的优点获得了出题者的青睐。此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。动态规划简介（DynamicProgramming）常州市第一中学林厚从动态规划简介动态规划中有很多深奥的概念，使用动态规划也有很多前提条件，它与递推、递归也有着密切的联系，这些都要等到我

7、们有一点编程经历后才好谈起，所以，我们先放开这些理论，不要被这些理论吓倒，而是去尝试分析和解决几个经典动态规划题目。学习动态规划最重要的是“一种思想方法和解题过程”，请大家积极动脑动手，跟着我一起分析和体会其中的方法和过程，然后再独立去思考和实践。常州市第一中学林厚从动态规划简介拦截导弹（NOIP1999）问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段

8、，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？样例输