oi-wiki读贴笔记:动态规划
Page content
此文是oi-wiki中字动态规划部分的总结。
1 要点
2 题目
2.1 入门
最长升序子序列
这个题目使用单调队列复杂度为O(nlogn),关键点在于序队列维护升序串,同时对于一个更小的输入,在队列中找到稍大于它的元素并进行替换。 帖子中表述有问题,队列中大于更小输入的元素不进行删除。
此文是oi-wiki中字动态规划部分的总结。
最长升序子序列
这个题目使用单调队列复杂度为O(nlogn),关键点在于序队列维护升序串,同时对于一个更小的输入,在队列中找到稍大于它的元素并进行替换。 帖子中表述有问题,队列中大于更小输入的元素不进行删除。