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
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
for(int i = 1; i <= n; i++){
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+1;
int a[N], S[N];
while(!q.empty() && (q.front() <
i - L2))
q.pop_front();
if(i - L1 >= 1){
while(!q.empty() && S[q.back()] <
S[i- L1])
int n,L1,L2,ans;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
q.pop_back();
q.push_back(i-L1);
}
cin >> n >> L1 >> L2;
for(int i = 1; i <= n; i++)
cin >> a[i];
S[i] = a[i] + (q.empty() ? 0 :
S[q.front()]);
deque<int> q;
ans = max(ans,S[i]);
ans = 0;
}
cout << ans;
}
6
6 trang
17420
Free
Bạn đang xem tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thuat_toan_ung_dung_chuong_5_phan_2_cau_truc_deque.pdf
