¶ Quy hoạch động chia để trị (Divide and Conquer DP)
Tác giả:
- Lê Minh Hoàng - Đại học Khoa học Tự nhiên, ĐHQG-HCM
Reviewer:
- Ngô Nhật Quang - THPT chuyên Khoa học Tự Nhiên, ĐHQGHN
- Nguyễn Minh Nhật - THPT chuyên Khoa học Tự nhiên, ĐHQGHN
- Nguyễn Minh Hiển - Đại học Công nghệ, ĐHQGHN
- Phạm Hoàng Hiệp - University of Georgia
¶ Giới thiệu
Bài viết "Tối ưu quy hoạch động 1 chiều" của tác giả Nguyễn Tuấn Tài trong Tạp chí VNOI Xuân Quý Mão (trang 16) đã đề cập đến một phương pháp tối ưu quy hoạch động rất đặc biệt, đó là phương pháp tối ưu quy hoạch động 1 chiều.
Trong bài viết này, ta sẽ tìm hiểu về một phương pháp tối ưu quy hoạch động khác, dùng cho các bài toán mà công thức truy hồi có dạng:
Công thức trên có độ phức tạp . Ta có thể tối ưu độ phức tạp xuống còn bằng phương pháp quy hoạch động chia để trị nếu hàm chi phí thoả mãn điều kiện áp dụng (được đề cập ở phần tiếp theo).
Ngoài ra, ta còn có thể tối ưu độ phức tạp của công thức trên xuống còn bằng Kĩ thuật bao lồi (Convex Hull Trick) nếu hàm chi phí thoả các điều kiện của kĩ thuật.
¶ Điều kiện áp dụng
Đầu tiên, ta định nghĩa lại bất đẳng thức tứ giác (quadrangle inequality) và điều kiện đơn điệu (monotonicity condition) như sau:
- Bất đẳng thức tứ giác:
- Bất đẳng thức tứ giác xuôi:
- Bất đẳng thức tứ giác ngược:
- Điều kiện đơn điệu:
- Đơn điệu tăng:
- Đơn điệu giảm:
Tiếp theo, ta định nghĩa mảng như sau:
Nói cách khác, là giá trị nhỏ nhất sao cho đạt giá trị cực tiểu.
Cuối cùng, để có thể áp dụng quy hoạch động chia để trị cho công thức đã được đề cập ở trên, mảng cần phải thoả mãn điều kiện đơn điệu (tuỳ bài toán mà ta cần đơn điệu tăng hay đơn điệu giảm, nhưng vì không mất tính tổng quát nên ta sẽ giả sử là đơn điệu tăng):
Nhưng đôi khi, việc chứng minh điều kiện đơn điệu cho một công thức truy hồi sẽ không hề dễ dàng. Trong một số bài toán, ta có thể chứng minh điều kiện đơn điệu thông qua bất đẳng thức tứ giác tương ứng (vì ta đang giả sử điều kiện đơn điệu là đơn điệu tăng nên bất đẳng thức tứ giác tương ứng là bất đẳng thức tứ giác xuôi) trên hàm chi phí :
Ta có thể chứng minh rằng, nếu hàm chi phí thoả mãn bất đẳng thức tứ giác, thì sẽ thoả mãn điều kiện đơn điệu tương ứng (phần chứng minh này sẽ được đặt ở cuối bài viết), tức là:
- Bất đẳng thức tứ giác xuôi Đơn điệu tăng
- Bất đẳng thức tứ giác ngược Đơn điệu giảm
Lưu ý rằng, ta không thể có được bất đẳng thức tứ giác từ điều kiện đơn điệu tương ứng, tức là mối quan hệ chỉ xảy ra một chiều.
¶ Thuật toán
¶ Ý tưởng
Ý tưởng chính của kỹ thuật này là dựa trên điều kiện .
Giả sử, ta vừa tính được trong bằng cách xét tất cả vị trí trong đoạn .
Xét , ta biết rằng . Do đó, ta có thể tính trong , thay vì , bằng cách xét tất cả vị trí trong đoạn .
¶ Thuật toán chia để trị
Dựa trên ý tưởng đó, ta có thuật toán chia để trị như sau:
- Đầu tiên, ta tính trong .
- Tiếp theo, ta tính (biết rằng ) và (biết rằng ), tổng độ phức tạp của "tầng" này là .
- Tiếp tục đệ quy để tính , trong quá trình đệ quy, ta duy trì cận trên và dưới của .
¶ Độ phức tạp
Phiên bản cũ
Giả sử độ phức tạp để tính chi phí là .
Vì sau khi xét một đoạn vị trí để tính , ta chia đoạn đó thành đoạn không giao nhau (đoạn bên trái có biên phải là , đoạn bên phải có biên trái là ) và tiếp tục đệ quy trên đoạn đó, nên tổng độ dài các đoạn thuộc mỗi "tầng" là và số "tầng" đệ quy tối đa là . Do đó:
- Tổng độ phức tạp để tính là .
- Tổng độ phức tạp của thuật toán sau lần tính là .
Xét , giả sử ta cần tính tất cả , biết rằng .
Đặt . Nếu độ phức tạp để tính chi phí là thì ta có thể tính trong .
Tiếp theo, ta gọi đệ quy để tính của đoạn:
- với
- với
Nếu bỏ qua thì rõ ràng là và không giao nhau, nên tổng chi phí để tính tất cả thuộc mỗi "tầng" là . Và vì ta luôn chia đôi đoạn cần tính ở mỗi lần đệ quy nên số "tầng" đệ quy là . Do đó:
- Tổng độ phức tạp để tính là .
- Tổng độ phức tạp của thuật toán sau lần tính là .
Dưới đây là hình minh hoạ về tổng độ phức tạp để tính :
¶ Cài đặt
Mặc dù việc triển khai có thể khác nhau tùy theo từng bài toán nhưng chúng đều có một cấu trúc chung.
Với mỗi lần tính , hàm solve() gọi compute(0, n, 0, n).
Mỗi khi được gọi, hàm compute tính và (dp_cur) dựa vào (dp_before) và hàm chi phí C.
int m, n;
vector<int> dp_before(n + 1), dp_cur(n + 1);
// hàm chi phí
int C(int l, int r);
// tính dp_cur[l], ..., dp_cur[r]
void compute(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) >> 1;
pair<int, int> best = { INT_MAX, -1 };
// tính dp_cur[mid] và opt[i][mid] dựa vào dp_before và hàm chi phí
for (int k = optl; k <= min(mid, optr); ++k) {
best = min(best, { dp_before[k] + C(k, mid), k });
}
dp_cur[mid] = best.first;
int opt = best.second;
// đệ quy để tính dp_cur[l..mid-1] và dp_cur[mid+1..r]
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
int solve() {
for (int i = 0; i <= n; ++i)
dp_before[i] = C(0, i);
for (int i = 1; i < m; ++i) {
compute(0, n, 0, n);
dp_before = dp_cur;
}
return dp_before[n];
}
¶ Ứng dụng
¶ Codeforces - 1601C (Optimal Insertion)
Cho mảng và .
Ta cần chèn các phần tử của mảng vào mảng một cách tuỳ ý (ở đầu, ở giữa, hoặc ở cuối). Kết quả là ta sẽ nhận được mảng có kích thước .
Nói cách khác, thứ tự của các phần tử của mảng trong mảng phải được giữ nguyên. Ngược lại, các phần tử của mảng có thể xuất hiện trong mảng theo bất kỳ thứ tự nào.
Hỏi số cặp nghịch thế ít nhất có thể của mảng là bao nhiêu? Biết rằng một cặp được gọi là nghịch thế nếu và .
Giới hạn:
¶ Ý tưởng
Đầu tiên, ta sắp xếp mảng tăng dần (để ).
Với mỗi , gọi là vị trí nhỏ nhất sao cho khi ta chèn vào trước thì số cặp nghịch thế tăng lên là ít nhất. Nếu chèn ở cuối mảng thì .
Ta có nhận xét: Nếu tồn tại và thì ta có thể đổi chỗ và để giảm số cặp nghịch thế (bạn đọc có thể tự chứng minh). Do đó, ta có .
Từ đây, ta có thể áp dụng quy hoạch động chia để trị để tìm giá trị của mảng , sau đó dựng mảng và tính số cặp nghịch thế.
Bài toán bây giờ là làm thế nào để tính nhanh giá trị khi có và .
Dễ chứng minh, số cặp nghịch thế tăng thêm được xác định bởi biểu thức sau:
Nếu biết trước và , rõ ràng và là như nhau với mọi vị trí , vậy nên ta có thể bỏ qua. Còn lại và , ta dựng mảng và để tính nhanh trong .
¶ Cài đặt
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int n, m;
int a[N], b[N], c[N * 2];
int p[N];
int prf[N], suf[N];
int bit[N * 2];
int calcPos(int optl, int optr, int bi) {
prf[optl - 1] = suf[optr + 1] = 0;
for (int i = optl; i <= optr; ++i) prf[i] = prf[i - 1] + (a[i] > bi);
for (int i = optr; i >= optl; --i) suf[i] = suf[i + 1] + (bi > a[i]);
int pos = optl;
for (int i = optl + 1; i <= optr; ++i)
if (prf[pos - 1] + suf[pos] > prf[i - 1] + suf[i]) pos = i;
return pos;
}
void compute(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) >> 1;
p[mid] = calcPos(optl, optr, b[mid]);
compute(l, mid - 1, optl, p[mid]);
compute(mid + 1, r, p[mid], optr);
}
void compress_c() {
vector<int> tmp(c + 1, c + n + 1);
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 1; i <= n; ++i)
c[i] = lower_bound(tmp.begin(), tmp.end(), c[i]) - tmp.begin() + 1;
}
void upd(int p, int v) {
for (; p; p ^= p & -p) bit[p] += v;
}
int get(int p) {
int res = 0;
for (; p <= n; p += p & -p) res += bit[p];
return res;
}
long long solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= m; ++i) cin >> b[i];
a[n + 1] = INT_MAX;
sort(b + 1, b + m + 1);
compute(1, m, 1, n + 1);
// dựng mảng c từ mảng a, b và p
for (int i = 1, j = 1, sz = 0; i <= n + 1; ++i) {
while (j <= m && p[j] == i) c[++sz] = b[j++];
if (i <= n) c[++sz] = a[i];
}
n += m;
compress_c();
fill(bit + 1, bit + n + 1, 0);
long long res = 0;
for (int i = 1; i <= n; ++i) {
res += get(c[i] + 1);
upd(c[i], 1);
}
return res;
}
int main() {
int test;
cin >> test;
while (test--) {
cout << solve() << '\n';
}
}
Độ phức tạp thời gian:
Độ phức tạp không gian:
¶ VNOJ - nkleaves (Leaves)
Ta có thể tóm tắt bài toán như sau:
- Cho mảng độ dài là trọng lượng của chiếc lá (đánh số từ đến ) và một số .
- Ta cần chia chiếc lá thành đúng đoạn liên tiếp (độ dài đoạn phải khác ), mỗi đoạn sẽ gom thành một đống lá ở vị trí trái cùng. Chi phí để di chuyển một chiếc lá bằng tích trọng lượng của chiếc lá và khoảng cách di chuyển. Nói cách khác, chi phí của một đống là .
- Yêu cầu: tìm chi phí nhỏ nhất để gom chiếc lá thành đúng đống lá.
Giới hạn:
- ,
¶ Ý tưởng
Đầu tiên, gọi là chi phí để gom những chiếc lá liên tiếp trong đoạn thành một đống lá ở vị trí trái cùng . Nói cách khác, .
Để tính nhanh , ta viết lại công thức như sau:
Ta tính trước mảng cộng dồn và để có thể tính trong .
Tiếp theo, đặt là chi phí tối thiểu để gom chiếc lá đầu tiên thành đống lá. Ta có công thức truy hồi với độ phức tạp thời gian cho bài toán này là
Vì hàm chi phí thoả bất đẳng thức tứ giác xuôi (bạn đọc có thể tự chứng minh) nên ta có thể áp dụng quy hoạch động chia để trị, giảm độ phức tạp thời gian xuống còn .
¶ Cài đặt
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, k;
int w[N], prf1[N];
long long prf2[N];
vector<long long> dp_before, dp_cur;
long long C(int l, int r) {
return (prf2[r] - prf2[l - 1]) - 1LL * l * (prf1[r] - prf1[l - 1]);
}
void compute(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) >> 1;
pair<long long, int> best = { LONG_LONG_MAX, -1 };
for (int i = optl; i <= min(mid, optr); ++i) {
best = min(best, { dp_before[i] + C(i + 1, mid), i });
}
dp_cur[mid] = best.first;
int opt = best.second;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
prf1[i] = prf1[i - 1] + w[i];
prf2[i] = prf2[i - 1] + w[i] * i;
}
dp_before.assign(n + 1, LONG_LONG_MAX / 2);
dp_before[0] = 0;
dp_cur.resize(n + 1);
for (int i = 1; i <= k; ++i) {
compute(i, n, i - 1, n - 1);
dp_before.swap(dp_cur);
}
cout << dp_before[n];
return 0;
}
Độ phức tạp thời gian:
Độ phức tạp không gian:
¶ Bài tập áp dụng
- Codeforces - 321E (Ciel and Gondolas)
- Codeforces - 834D (The Bakery)
- Codeforces - 868F (Yet Another Minimization Problem)
- Atcoder - ARC067D (Yakiniku Restaurants)
- Codechef - CHEFAOR (Chef and Bitwise OR Operation)
- Kattis - Famous Pagoda
- Hackerrank - Guardians of the Lunatics
- Hackerrank - Mining
¶ Liên hệ giữa bất đẳng thức tứ giác và điều kiện đơn điệu
Vì không mất tính tổng quát, trong phần này, ta sẽ chứng minh rằng, nếu hàm chi phí thoả mãn bất đẳng thức tứ giác xuôi , thì sẽ thoả mãn đơn điệu tăng .
Ta sẽ chứng minh điều này bằng phép phản chứng: giả sử tồn tại vị trí thoả .
Để thuận tiện cho việc chứng minh, ta đặt , , và . Ta có:
Lấy trừ , ta được:
Áp dụng bất đẳng thức tứ giác cho hàm chi phí với bộ số , ta có:
Điều này là vô lý. Do đó, ta có được điều phải chứng minh.