分析
我们先确定我们的状态存储,利用f存储在i这个长度下标的最长上升子序列的长度。那么我们如何更新下一个长度下标i的长度呢?我们就可以找出不大于它的最长的长度下标,在这个基础上加上1就好了。
代码
1 | #include <iostream> |
优化
在更新的过程中有个寻找的过程,要找到最大的并且数字不大于当前数字的那个长度所在的下标。寻找过程可以尝试用二分替代。
里面的动图一看就懂
1 | #include <iostream> |
====================================
再论二分
yxc的代码里的二分实属把我惊到了,我之前接触的二分完全就是一个死公式,完全不能灵活变通,经过一段时间的思考,我想我大概弄明白了二分的本质
1 | int mid=l+r>>1; |
1 | int mid=l+r+1>>1; |
这两个东西不是针对某一个问题的死方法,而因该说是避免进入死循环的两种写法。我总结了一下什么时候该套用两种模板的方法。
首先二分我们只考虑二分的最后几个步骤,一个是卡位操作(我姑且就这么说),另外一个是逼近操作(也姑且就这么说),卡位操作需要的是“l=mid+1”和“r=mid-1”这两个操作,这两个是专门用来卡住位置的,另外就是条件的设置。
以这道题为例,我们想找到第一个不大于这个数的数,我们先试试用l=mid+1来试试怎么卡位置,我么发现
无论是<还是<=都无法卡出我们想要的那个位置,<的时候,l=mid+1会将数字刚好移到这个数字上,最终结果将是等于或者是第一个大于这个数的数,<=的时候只会得到第一个大于它的数。
之后是r=mid-1,条件设置为>最终结果将是第一个小于它或者是等于它的数,<=则就是第一个小于它的数字,这样条件就确定完了。
最后根据我们确定的卡位的公式套用相应的模板就可以完成操作了。
二分
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/11/%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97DP/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!