历届NOIp动态规划梳理技术总结.ppt

历届NOIp动态规划梳理; 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，以得到全局最优策略。 动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来，动态规划几乎每次都出现在NOIp的赛场上，而且还有越来越多的趋势。因此，掌握基本的NOIp动态规划题是至关重要的。;动态规划实质：;Sample Problem1; 我们先将NOIp里的动态规划分分类：;最长不降子序列;;最长不降子序列;最长不降子序列;最长不降子序列;最长不降子序列;最长不降子序列;最长不降子序列;最长不降子序列;背包;背包;背包;背包;背包;背包;方格取数;方格取数;方格取数; 我们观察一下它的路径。f[i,j]是从f[i-1,j]或者f[i,j-1]走来。无论是从f[i-1,j]还是f[i,j-1]走来，要么是x坐标+1，要么是y坐标+1，总归x坐标的值+y坐标的值一定比前一个多1。 我们来验证一下：;方格取数;方格取数;方格取数;石子归并;石子归并;石子归并;石子归并;石子归并;石子归并;石子归并;Sample Problem11;石子归并;Sample Problem12; 改变一下题目的叙述：每行有m个数，倒数第i次取的得分是a[i]*2^(m+1-i)；倒推，因为每次只能取一段中的头或尾，所以剩下的永远是连续的一段，每次加入头或尾。 把一段的头和尾看做一堆石子，把a[i]*2^(m+1-i)看做每次归并的加分，每次归并不是取相邻的，而是取一段中的头或尾——就是石子归并。 用f[i,j,k]表示第i行，取了一些数后剩下连续的一段从j到k，那么状态转移方程就很好写了： f[i,j,k]:=Max{f[i,j-1,k]+a[j-1]*2^(m-k+j-1) f[i,j,k+1]+a[k+1]*2(m-k+j-1)}; 这道题目还要高精度，建议写好非高精的DP再修 改成高精度的。;状态压缩;状态压缩;状态压缩;第二种情况：st 我们先来看一组数据。s=4，t=5。; 假设s=3，t=5，那么11=3+4+4就也可以到达了。所以，只有当t=s+1时，连续的点的起始位置才能尽量后面。最坏情况就是s=9，t=10了（仔细想想为什么？）。 跟前面的s=4，t=5的情况一样，其实s=9，t=10时只要一段没有石头的区间长度在90之外，我们都把它当做90对待就可以了。 因此，我们每次对于一段没有石头的区间长度为x，如果x=t(t-1)，我们仍然把它当做x来处理；相反，当xt(t-1)时，我们就把它当做t(t-1)处理。这样，最大的复杂度就是t(t-1)*（石头个数+1）=90*101=9090，比之前的复杂度大大降低。 这种方法叫状态压缩，我们这题用的方法叫离散 化。至此，过河完美AC！;Sample Problem14; 应该明确这是一道数学题，数学题往往有明显或暗藏的规律可以快速求得解。在NOIp中数学递推题并不常见，但不能排除它出现的可能性。对于这类问题，我们不能盲目找规律，而要细细寻找每个状态之间的内在联系，从而一步一步求得最终要求的答案。此类问题一般要用到数学公式、数学证明、方程变形、极端化等思想，根据题目的不同适当选取方法。 根据前面讲的，有几个枚举量我们就设几个状态，这道题目明显n和k都是枚举量，要求的几种方案是值，因此建立起递推状态：f[i,j]表示将i分成j份的方案数。 接下来就是写出状态转移方程了，一旦状态转移方程写出，那么f[i,j]就可以由f[x,y]等其他状态得来，因为得到最后我们要求得f[n,k]。;数学递推;数学递推;数学递推; f[i,j]:=f[i-j,1]+f[i-j,2]…+f[i-j,j];;Sample Problem15; 因为此题给我们的是中序遍历，所以如果a[i]为根，那么a[1]~a[i-1]就是这棵树的左子树，a[i+1]~a[n]就是这棵树的右子树。同样的如果j是a[1]~a[i-1]这棵子树的根，那么a[1]~a[j-1]就是左子树中的左子树，a[j+1]~a[i-1]就是左子树中的右子树，依次类推。 这样，我们只要枚举i~j这个区间和枚举这个区间的根k就可以了。至于路径，记录一下就可以了。; 总结： 动态规划是NOIp中的一类大问题