飞扬的小鸟题解p1941

看到这个题目，偷看一眼标签，发现了dp。由于老师上课讲了，我现在就总结一下这题。 首先，确定使用dp（看到题解里有人宽搜过，不过有可能我记错了），那么确定它的状态 假设我们可以完全通过，定义一个数组f[[i][j]，表示从开始到坐标(i,j),最少跳几次。很容易的我们可以得到这么一个状态转移方程f[i][j]=min(f[i][j],f[i-1][j-x[i-1×q]+q)(q>=0) 确保 j-x[i-1]×q>0 同时还有一个f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]) ？？？真的这么简单吗 当然不是，这是道典型的细节题，不知道读者有没有注意到当跳到最高高度时是不能向上跳的（用我们老师的话说，关键是在天花板上死不掉） （ps：！！！！注意注意：咳咳，在我们的游戏里似乎跳到最高处继续跳是掉不下来的，这里声明，我们的程序里是不会出现这种情况的，请直接忽略） 好的我们继续，如何给天花板特判呢，是这样的 if(j==m)//特判到了顶部 for(int z=m-up[i-1];z<=m;z++) { f[i][j]=min(f[i][j],f[i-1][z]+1); //一次跳到顶部 f[i][j]=min(f[i][j],f[i][z]+1); //两次或以上跳到顶部 } 读者有没有理解三句注释的含义呢，如果没有的话估计是第三句吧，什么叫两次或以上 。是这样的，f[i][z]是跳到(i,z)的最少触摸次数,这个时候我们明显还能跳,但注意循环的开始处int z=m-up[i-1]，这就是说我们再跳必定顶到顶部，因而直接加1再比较就好了 既然顶部处理结束了，那么是不是就能A了呢？不对，这种算法时间复杂度依旧过高，我们仍然需要进一步优化（这样好像据说是70分左右，我也不知道） 怎么优化呢？当然是看看dp了，好的这就是优化的核心，仔细观察f[i][j],f[i][j-x[i-1]],f[i][j-2*x[i-1]].....好吧看出规律了么，这里我借老师的课件上的例子一用 举例，假设Xi=3 f[3,10]= min{f[2,7]+1, _f[2,4]+2, f[2,1]+3_ } f[3,7]= min{f[2,4]+1, _f[2,1]+2_ } f[3,4]= min{f[2,1]+1} 比较后面一部分和前面一个的关系，没错就是加1 代码：f[i][j]=min(f[i][j],f[i][j-up[i-1]]+1);//优化的重要步骤 已经很清楚了吧