动态规划Yes.ppt

动态规划?Yes!——BySherlock小羊头啃苹果Sherlock最近认识了一只很可爱的牧羊犬,自称小羊头。她很喜欢吃苹果,常常偷偷溜到Sherlock的花园来瞻仰种在那儿的两棵苹果树。然而小羊头实在太小了,够不着苹果树上的苹果。于是Sherlock只好施展魔法,使得每分钟都有一只苹果从两棵树的其中一棵上掉下来。众所周知,苹果掉到地上是会烂掉的,而没人喜欢吃烂苹果,因此小羊头只有在苹果掉落时站在苹果树下才能接住苹果并狼吞虎咽之。她吃苹果速度非常快,完全可以忽略不计,而且她跑步也很快,从一棵树跑到另一棵树所花的时间同样也可以忽略不计,然而她却非常懒,只愿意跑W(W<=30)次。现今苹果已经开始掉落了,小羊头正站在A树底下,而且我们知道Sherlock目前还只是个菜鸟巫师,MP(魔法值)有限,所以该法术只能撑T(1<=T<=1000)分钟。聪明的你可以帮助小羊头在这T分钟内吃到最多的苹果么?输入第一行:包含两个整数,T和W第二至T+1行:1或者2,分别表示该时刻苹果从A树或者B树上掉落输出仅一行:小羊头所能吃到的最多的苹果数样例输入:722112211样例输出:6输入输出什么是动态规划?动态规划(DynamicProgramming)是近年来不管在OI还是ACM赛场上都大行其道的热门算法。动态规划题往往可以转化为解搜索树的问题,同样是搜索树,动态规划却比搜索算法高效很多,因为它把每个状态的最优值都记录了下来,于是成功地避免了重复地处理重叠子问题。不过,动规的使用要满足两个基本条件:使用动态规划所需满足的基本条件最优子结构用动态规划解决一个问题的第一步是刻画一个最优解的结构。如果一个问题的最优解中包含了子问题的最优解,我们就说这个问题具有最优子结构无后效性动态规划的过程是一个状态转移的过程:不断地从一个已知的状态出发,推出一个新的状态。但是,如果新的状态又能推出前面的状态(影响前面的状态),那么这样的状态划分就具有了后效性。动态规划能够成功的一个必要条件就是无后效性。先感受一下递推小羊头吃饱苹果后要减肥,于是选择爬楼梯。已知小羊头每次可以跨上1…M个台阶,而此楼梯一共有N个台阶,问小羊头从最底下爬到最高处有几种爬法(没人要求牧羊犬跳楼梯吧)?答案:设f[i]为爬上i个台阶的方案数那么:f[i]=sigma(f[i–j])(1<=j<=min(i,m))最后f[n]即为所求解很简单吧~回忆一下开篇那题首先提取问题模型:若相邻的数字均为1或者2,那么不妨把这些苹果合并起来,得到某一段时间某一棵树连续掉落的苹果数那么此问题就转化为:已知一串数字,从中提取部分数相加,约定奇偶位相间取的次数不能超过W次,求最大和注意小羊头刚开始是站在A树下的,初始化时需要做相关操作思考过程思考每一个状态需要保留哪些信息思考某一个状态与先前哪些状态有关,可以由哪些状态推出构建方程思考该方程是否满足两个基本条件搞定了么?No!仔细检查方程初始化、上下界部分是否正确解答F[i,j]表示到第i个数为止,已经奇偶相间提取了j次,所得的最大和A[i]表示第i个数的值F[1][0]=A[1]F[i,j]=max(f[i–1][j–1],f[i–2][j])+A[i]