单调队列优化

dp 单调队列优化

T1 P6033 [NOIP2004 提高组] 合并果子 加强版

题目描述：

给定 \(n\) 个数,每次可以将两个数合并并获得为两数和的分数,求合并到只剩一个数时的最小总分数.
\(1 \le n \le 10^7 \quad 1 \le a_i \le 10^5\)
思路：

新知识1 : 双端队列 :

1. deque<int>q;

复制代码

速度更快,支持双端操作,支持使用类似于数组的方式 \((q[k])\) 访问.
常用函数:

1. //入队
2. q.push_back(k);
3. q.push_front(k);
4. q.emplace_back(k);//速度更快,仅限C++14使用
5. q.emplace_front(k);//速度更快,仅限C++14使用
6. //出队
7. q.pop_front();
8. q.pop_back();
9. //调用
10. q.front();
11. q.back();
12. q[k];
13. //数据
14. q.empty();
15. q.size();

复制代码

新知识2 : 双端队列的迭代器----读取队列中的所有数据 :

[code]//读取队列中的所有数据for(auto i:q) cout