动态规划讲解课件

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

1、历届NOIp动态规划讲解动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，以得到全局最优策略。动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来，动态规划几乎每次都出现在NOIp的赛场上，而且还有越来越多的趋势。因此，掌握基本的NOIp动态规划题是至关重要的。动态规划实质：枚举+递推状态状态转移方程SampleProblem113591从树的根到树的叶节点，最多能取多少数？贪心：答案错误暴力搜索：如果数据大会超时动态规划！我们

2、先将NOIp里的动态规划分分类：最长不降子序列背包方格取数石子归并状态压缩数学递推顺序递推最长不降子序列设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j)(i，j<=n)例如3，18，7，14，10，12，23，41，16，24。若存在i1

3、[i]<=a[j])And(f[i]Ti+1>…>TK(1<=i<=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分

4、隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高。【输出文件】输出文件包括一行，这一行只包含一个整数，就是最少需要几位同学出列。SampleProblem2最长不降子序列最长不降子序列最长不降子序列最长不降子序列依此类推最长不降子序列拦截导弹（NOIp1999）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于

5、30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）SampleProblem3最长不降子序列第一问：最长下降子序列。第二问：DP？反例：987110654最长不降子序列987110654DP：98711065411011010103次！最长不降子序列987110654贪心：2次！98711065410654DP不是万能的！10654背包01背包：有N件物品和一个容量为V的背包。第i件物品的费用是c[i

6、]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。Fori:=1TonDoForj:=MaxDowntoa[i]Do(a[i]ToMax)Iff[j]

7、兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要