Bài giảng Thuật toán ứng dụng - Chương 5, Phần 2: Cấu trúc Deque - Phạm Quang Dũng

Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn THUẬT TOÁN ỨNG DỤNG 1 CẤU TRÚC DEQUE 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  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 using namespace std; const int N = 1e6+1; int a[N], S[N]; int n,L1,L2,ans; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> L1 >> L2; for(int i = 1; i <= n; i++) cin >> a[i]; deque q; ans = 0; 6 for(int i = 1; i <= n; i++){ while(!q.empty() && (q.front() < i - L2)) q.pop_front(); if(i - L1 >= 1){ while(!q.empty() && S[q.back()] < S[i- L1]) q.pop_back(); q.push_back(i-L1); } S[i] = a[i] + (q.empty() ? 0 : S[q.front()]); ans = max(ans,S[i]); } cout << ans; }