NOIp动态规划梳理-课件PPT（演示稿）.ppt

动态规划( dynamic programming) 是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,以得到全局最优策略。动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来,动态规划几乎每次都出现在 NOIp 的赛场上,而且还有越来越多的趋势。因此,掌握基本的 NOIp 动态规划题是至关重要的。动态规划实质: 枚举+ 递推状态状态转移方程 Sample Problem1 13591 从树的根到树的叶节点,最多能取多少数? 贪心:答案错误暴力搜索:如果数据大会超时我们先将 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<i2<i3< …< ie且有 a(i1)<a(i2)< …<a( ie)则称为长度为 e的不下降序列。如上例中 3, 18,23,24就是一个长度为 4的不下降序列,同时也有 3,7,10,12,16,24长度为 6的不下降序列。最长的不下降序列就是求长度最长的子序列。 For i:=1 To n Do For j:=1 To i-1 Do If (a[i]<=a[j])And(f[i]<f[j]+1) Then f[i]:=f[j]+1; 合唱队形( NOIp2004 ) 【问题描述】 N 位同学站成一排,音乐老师要请其中的(N-K) 位同学出列,使得剩下的 K 位同学排成合唱队形。合唱队形是指这样的一种队形:设 K 位同学从左到右依次编号为 1,2…, K, 他们的身高分别为 T1,T2,…,TK, 则他们的身高满足 T1<...<Ti>Ti+1> …>TK(1<=i<=K) 。你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。【输入文件】输入文件第一行是一个整数 N(2<=N<=100) , 表示同学的总数。第一行有 n 个整数,用空格分隔,第 i个整数 Ti(130<=Ti<=230) 是第 i位同学的身高。【输出文件】输出文件包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 Sample Problem2