本文从WordPress迁移而来, 查看全部WordPress迁移文章
线段树 dp
题意:略
思考:
- 从左至右读入元素并且更新,就可以保证当前这个元素,只受前面的元素影响。
- 换一个思路,当前元素为num[i],由于构建的还是还是LIS,所以在它前面的元素一定要比它小,如果我们能够知道以每个值结尾的LIS就好了,所以用Max[x]表示以x这个值结尾的LIS的最长长度,如果当前要构建以num[i]这个值结尾的LIS,那么只需要在[0,num[i]-1]里面查找到最大的Max[x]即可,但是,找到的这个Max[x]未必是合法的因为,未必距离当前值num[i]的位置大于d,所以采用一种滞后更新的思想,在处理num[i]的时候,这个元素前面d个元素的信息还不能更新,等处理完num[i]再逐一更新
- 另外dp[i]记录的是,以序列中第i个元素结尾的LIS的长度,上面提到的Max[i]用一个先单数来维护,具体看代码
1 |
|