THUẬT TOÁN ỨNG DỤNG CHIA ĐỂ TRỊ 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn NộI dung  Tổng quan chia để trị  Ví dụ minh họa  Độ phức tạp chia để trị  Giảm để trị 2 Tổng quan chia để trị  Chia bài toán cần giải ban đầu thành các bài toán con độc lập nhau  Giải (trị) các bài toán con  Tổng hợp lời giải của các bài toán con để dẫn ra lời giải của bài toán xuất phát 3 Ví dụ minh họa  Bài toán dãy con dài nhất: cho dãy số nguyên a = a1, a2, …, an. Tìm dãy con gồm một số liên tiếp các phần tử có tổng lớn nhất  Phân chia: ký hiệu P(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,…, aj có tổng cực đại  Tổng hợp lời giải  Ký hiệu PL(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,…, aj sao cho phần tử cuối cùng là aj có tổng cực đại  Ký hiệu PR(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,…, aj sao cho phần tử đầu tiên là ai có tổng cực đại 4 Ví dụ minh họa  Xét đoạn [l,l+1,...,r]. Ký hiệu m = (l+r)/2  P(l,r) = MAX{P(l, m), P(m+1,r), PL(l,m) + PR(m+1,r)} l P(l,m) m m+1 PR(m+1,r) PL(l,m) 5 P(m+1,r) r Ví dụ minh họa #include <bits/stdc++.h> using namespace std; #define INF 1e9 #define MAX 1000000 int a[MAX]; int n; void input(){ cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; } 6 Ví dụ minh họa int PL(int l, int r){ int rs = -INF; int s = 0; for(int i = r; i >= l; i--){ s += a[i]; rs = max(rs,s); } return rs; } int PR(int l, int r){ int rs = -INF; int s = 0; for(int i = l; i <= r; i++){ s += a[i]; rs = max(rs,s); } return rs; } 7 Ví dụ minh họa int P(int l, int r){ if(l == r) return a[r]; int m = (l+r)/2; return max(max(P(l,m),P(m+1,r)), PL(l,m)+P