oi-wiki读贴笔记:动态规划

Page content

此文是oi-wiki中字动态规划部分的总结。

1 要点

2 题目

2.1 入门

最长升序子序列

这个题目使用单调队列复杂度为O(nlogn),关键点在于序队列维护升序串,同时对于一个更小的输入,在队列中找到稍大于它的元素并进行替换。 帖子中表述有问题,队列中大于更小输入的元素不进行删除。