单调队列优化
dp 单调队列优化T1 P6033 合并果子 加强版
题目描述：
给定 \(n\) 个数,每次可以将两个数合并并获得为两数和的分数,求合并到只剩一个数时的最小总分数.
\(1 \le n \le 10^7 \quad 1 \le a_i \le 10^5\)
思路：
新知识1 : 双端队列 :
deque<int>q;速度更快,支持双端操作,支持使用类似于数组的方式 \((q)\) 访问.
常用函数:
//入队
q.push_back(k);
q.push_front(k);
q.emplace_back(k);//速度更快,仅限C++14使用
q.emplace_front(k);//速度更快,仅限C++14使用
//出队
q.pop_front();
q.pop_back();
//调用
q.front();
q.back();
q;
//数据
q.empty();
q.size();新知识2 : 双端队列的迭代器----读取队列中的所有数据 :
//读取队列中的所有数据for(auto i:q) cout
页:
[1]