- 首先 \(O(n \log n)\) 的贪心很好想,显然用堆,每次合并两个权值最小的即可
- 然后考虑 \(O(n)\) 怎么做?我们发现这个权值 \(\max(a_i,a_{i+1})\) 的 \(\max\) 很不好处理,因此我们考虑把他优化一下
- 使用单调栈可以求出权值为 \(a_i\) 的合并区间,然后我们发现对于合并一个区间答案时肯定是让 \(a_i\) 与 \(\min(l,r)\) 合并
- 最终注意要 \(- \infty\)
- 复杂度 \(O(n)\)
51nod 2620 序列问题
发布时间 2023-12-02 23:05:04作者: FOX_konata