THUẬT TOÁN ỨNG DỤNG CẤU TRÚC DEQUE 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn DEQUE  Cấu trúc dữ liệu tuyến tính có tính chất của cả ngăn xếp và hàng đợi:  Thêm 1 phần tử vào cuối deque  Lấy 1 phần tử ở đầu deque ra  Lấy 1 phần tử ở cuối deque ra  Trong C++  Khai báo: deque<int>  Phương thức: push_back(), push_front(), pop_front(), pop_back(), back(), front(), empty() 2 Quy hoạch động sử dụng deque  Cho dãy a1, a2, …, an và 2 số nguyên dương L1 < L2. Hãy tìm dãy con 1 ≤ j1 < j2 < … < jk ≤ n sao cho L1 ≤ jq+1 jq ≤ i2 và , , …, có tổng cực đại 3 Quy hoạch động sử dụng deque  Định nghĩa bài toán con  S(i): tổng cực đại của dãy con của dãy a1, …, ai thỏa mãn đề bài mà phần tử cuối cùng là ai  Công thức quy hoạch động  S(i) = max(ai + S(j) | L1 ≤ i – j ≤ L2} 4 Quy hoạch động sử dụng deque  Định nghĩa bài toán con  S(i): tổng cực đại của dãy con của dãy a1, …, ai thỏa mãn đề bài mà phần tử cuối cùng là ai  Công thức quy hoạch động  S(i) = max(ai + S(j) | L1 ≤ i – j ≤ L2}  Khởi tạo deque, lưu trữ các chỉ số j sao cho S(j) không tăng và là ứng cử viên để tính toán các bài toán con S(i)  Mỗi khi xét đến chỉ số i (i = 1,…, n) thì  Đưa hết các chỉ số j ở đầu deque tại đó j < i – L2 ra ngoài (vì nó ko là ứng cử viên để xác định S(i), S(i+1),…)  Đưa hết các chỉ số j ở cuối deque tại đó S(j) < S(i-L1) (do những chỉ số j như vậy không có ý nghĩa nữa trong việc xác định S(i), S(i+1),… 5 Quy hoạch động sử dụng deque #include <bits/stdc++.h> for(int i = 1; i <= n; i++){ using namespace std; while(!q.empty() && (q.front() < i - L2)) const int N = 1e6+1; q.pop_front(); int a[N], S[N]; if(i - L1 >= 1){ int n,L1,L2,ans; while(!q.empty() && S[q.back()] < int main(){ S[i- L1]) ios_base::sync_wi