Người viết: Nguyễn Tuấn Tài - Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia TP.HCM
Giới thiệu: đây là kiến thức xuất hiện trong đề thi TST 2022, và đã lấy đi rất nhiều nước mắt của thí sinh. Nếu bạn muốn thử học một thuật toán mới lạ mà nhiều người chưa biết, thì đây chính là bài viết dành cho bạn!
Khi làm những bài toán quy hoạch động, đôi khi ta sẽ nghĩ ra những thuật toán có độ phức tạp rất lớn, ví dụ:
Ở bài viết này, chúng ta sẽ tìm hiểu về cách tối ưu công thức thứ , hay còn gọi là phương pháp tối ưu quy hoạch động chiều.
Gọi là một hàm tính cost thỏa mãn bất đẳng thức tứ giác (quadrangle inequality):
với mọi .
Ta sẽ tính toán công thức quy hoạch động sau với độ phức tạp nhanh hơn :
Một số ví dụ về hàm thỏa mãn bất đẳng thức tứ giác (bạn đọc có thể tự chứng minh):
Nhưng... làm sao để tối ưu công thức quy hoạch động trên? Có cách nào để nhanh chóng tìm được vị trí mà đạt giá trị nhỏ nhất không?
Ta định nghĩa mảng như sau
với là chỉ số để đạt giá trị nhỏ nhất.
Nói cách khác, là vị trí nhỏ nhất thỏa mãn đạt giá trị cực tiểu.
Để thuận tiện cho việc biểu diễn thuật toán, ta sẽ quy ước
, .
Trước khi đi vào thuật toán chính, chúng ta sẽ xem xét qua thuật toán "ngây thơ" sau:
Ở thời điểm đầu tiên,
.
Ở thời điểm thứ :
Chúng ta có thể cài đặt thuật toán trên một cách đơn giản như sau:
const int N = 1e5 + 3;
int n, h[N];
long long f[N];
long long w(int j, int i) {
// một hàm cost bất kì thỏa mãn
// bất đẳng thức tứ giác
}
void solve() {
for (int i = 1; i <= n; ++i) {
// cập nhật f[i]
f[i] = f[h[i]] + w(h[i], i);
for (int j = i + 1; j <= n; ++j) {
// cập nhật lại h[i + 1..n]
if (
f[i] + w(i, j) < f[h[j]] + w(h[j], j)
) {
h[j] = i;
}
}
}
}
Dễ thấy thuật toán "ngây thơ" trên có độ phức tạp . Làm sao để cải tiến thuật toán? Liệu mảng có một tính chất đặc biệt nào có thể giúp ta dễ dàng cập nhật được không?
Nhận xét . Ở mọi thời điểm, mảng luôn là dãy đơn điệu tăng (tức . (chứng minh ở phần Phụ lục)
Việc mảng luôn là dãy đơn điệu tăng sẽ có ý nghĩa gì?
Khi cập nhật đến , nếu tồn tại một vị trí thỏa mãn , điều đó đồng nghĩa với việc sẽ không thay đổi. Không chỉ thế, vì , nên cả đoạn cũng sẽ không thay đổi.
Hệ quả. Nếu tồn tại vị trí thỏa mãn , ta được với mọi .
Chính vì thế, để cập nhật mảng , ta sẽ tìm vị trí nhỏ nhất thỏa mãn , và cập nhật . Từ đây, ta có ý tưởng thuật toán sau:
Thuật toán.
Ta sẽ biểu diễn mảng thành đoạn thỏa mãn:
Ta có thể cài đặt thuật toán trên bằng cách sử dụng deque. Để thuận tiện cho việc cài đặt, ta sẽ không lưu lại các giá trị đã qua sử dụng.
struct item {
int l, r, p;
};
const int N = 1e5 + 3;
int n;
long long f[N];
long long w(int j, int i) {
// một hàm cost bất kì thỏa mãn
// bất đẳng thức tứ giác
}
void solve() {
deque<item> dq;
dq.push_back({1, n, 0});
for (int i = 1; i <= n; ++i) {
f[i]=f[dq.front().p]+w(dq.front().p,i);
// deque chỉ lưu giá trị từ h[i + 1]
// tới h[n]
++dq.front().l;
// nếu l > r, ta loại đoạn này khỏi deque
if (dq.front().l > dq.front().r) {
dq.pop_front();
}
while (!dq.empty()) {
auto [l, r, p] = dq.back();
if (f[i] + w(i, l) < f[p] + w(p, l)) {
dq.pop_back();
// p không còn là giá trị của
// h[l], h[l + 1], ..., h[r]
// lúc này, h[l]=h[l+1]=...=h[r]=i.
}
else break;
}
if (dq.empty()) {
dq.push_back({i + 1, n, i});
// h[i+1]=h[i+2]=...=h[n]=i
}
else {
// tìm nhị phân vị trí pos nhỏ nhất
// thỏa mãn h[pos] = i
auto& [l, r, p] = dq.back();
int low = l, high = r;
int pos = r + 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (f[i] + w(i, mid) < f[p] + w(p, mid)) {
pos = mid, high = mid - 1;
}
else {
low = mid + 1;
}
}
// cập nhật đoạn (l,r,p) thành (l,pos-1,p)
r = pos - 1;
if (pos <= n) {
dq.push_back({pos, n, i});
// h[pos]=h[pos+1]=...=h[n]=i
}
}
}
}
Vì số đoạn tối đa được thêm vào deque trong cả quá trình là , kết hợp với tìm kiếm nhị phân ở cuối mỗi thời điểm, ta được độ phức tạp cuối cùng là .
Cho cây được đánh số hiệu từ tới , mỗi cây có độ cao lần lượt là . Alob và Bice muốn cưa đổ tất cả cây sao cho tốn ít chi phí nhất.
Alob và Bice có một cái cưa máy, mỗi lần sử dụng cưa có thể giảm độ cao của một cây bất kì xuống . Tuy nhiên, sau mỗi lần sử dụng, cưa máy cần được sạc lại. Chi phí để sạc phụ thuộc vào những cây đã được chặt hoàn toàn (những cây đã được giảm độ cao về ): trong những cây đã được chặt hoàn toàn, giả sử cây có số hiệu lớn nhất là , chi phí để sạc cưa máy là . Nếu không có cây nào đã được chặt hoàn toàn, ta không thể sạc lại cưa máy.
Điều kiện bài toán:
Vì , ta sẽ tìm chi phí nhỏ nhất để chặt hoàn toàn cây (sau đó, ta có thể chặt bất kì cây nào mà không tốn chi phí).
Gọi là chi phí nhỏ nhất để chặt hoàn toàn cây thứ . Nếu cây gần nhất được chặt hoàn toàn trước đó là , chi phí nhỏ nhất để chặt hoàn toàn cây thứ sẽ là . Vì vậy, ta có được công thức quy hoạch động sau:
Nếu đặt , hàm là một hàm thỏa mãn bất đẳng thức tứ giác.
Chứng minh.
Xét điểm , ta có:
Vì vậy,
Từ đây, ta có thể áp dụng thuật toán đã nêu trong bài.
#include <bits/stdc++.h>
using namespace std;
struct item {
int l, r, p;
};
const int N = 1e5 + 3;
int n, a[N], b[N];
long long f[N];
long long w(int j, int i) {
return 1LL * b[j] * a[i];
}
void solve() {
deque<item> dq;
dq.push_back({2, n, 1});
for (int i = 2; i <= n; ++i) {
f[i] = f[dq.front().p] + w(dq.front().p, i);
++dq.front().l;
if (dq.front().l > dq.front().r) {
dq.pop_front();
}
while (!dq.empty()) {
auto [l, r, p] = dq.back();
if (f[i] + w(i, l) < f[p] + w(p, l)) {
dq.pop_back();
}
else break;
}
if (dq.empty()) {
dq.push_back({i + 1, n, i});
}
else {
auto& [l, r, p] = dq.back();
int low = l, high = r, pos = r + 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (f[i] + w(i, mid) < f[p] + w(p, mid)) {
pos = mid, high = mid - 1;
}
else {
low = mid + 1;
}
}
r = pos - 1;
if (pos <= n) {
dq.push_back({pos, n, i});
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
solve();
cout << f[n];
}
Ở ngôi làng nọ, có ngôi nhà nằm trên một đường thẳng. Biết trưởng làng sống ở nhà thứ , nhà thứ nằm cách nhà trưởng làng đúng km về phía đông. Trưởng làng muốn chọn ra một số địa điểm trên đường thẳng để chuẩn bị tổ chức lễ hội, biết chi phí tổ chức lễ hội cho một địa điểm là .
Sau khi chuẩn bị xong, tất cả người dân sẽ di chuyển đến địa điểm gần nhà mình nhất để tham gia lễ hội. Nếu một người dân ở cách địa điểm tổ chức km, chi phí để di chuyển sẽ là .
Hãy tìm cách chọn một số địa điểm sao cho tổng chi phí tổ chức lễ hội và di chuyển là nhỏ nhất.
Nói cách khác, nếu như ta chọn địa điểm, địa điểm thứ nằm cách nhà trưởng làng đúng km về phía đông, tổng chi phí tổ chức lễ hội và di chuyển sẽ là .
Điều kiện bài toán:
Ta có nhận xét sau: tất cả người dân nằm trên một đoạn liên tiếp sẽ đến cùng một địa điểm, vì thế bài toán có thể viết lại thành: chia người dân thành các đoạn liên tiếp sao cho tổng chi phí là nhỏ nhất, biết chi phí mỗi đoạn gồm chi phí tổ chức và chi phí di chuyển của người dân trong đoạn.
Gọi là chi phí nhỏ nhất để chia người dân thành các đoạn sao cho tổng chi phí là nhỏ nhất. Ta có công thức quy hoạch động sau:
với là chi phí di chuyển của người dân nằm trong đoạn tới .
Ta sẽ chứng minh hàm thỏa mãn bất đẳng thức tứ giác.
Chứng minh.
Đặt số người dân trong đoạn là .
Đặt . Ta có trường hợp sau:
Nếu chẵn, phương án đặt địa điểm tập trung tối ưu nhất là ở giữa người thứ và người thứ .
Chi phí di chuyển trong trường hợp này là , hay .
Ngược lại, phương án đặt địa điểm tập trung tối ưu nhất là ở nhà của người thứ .
Chi phí di chuyển trong trường hợp này là , hay .
Xét điểm . Để thuận tiện cho việc chứng minh, ta sẽ giả sử độ dài các đoạn đều là chẵn. Các trường hợp còn lại cũng có thể chứng minh tương tự.
Với chẵn: .
Đặt , , , . Ta có:
Vì vậy,
#include <bits/stdc++.h>
using namespace std;
struct item {
int l, r, p;
};
const int N = 2e5 + 3;
int n, k, a[N];
long long p[N], f[N];
long long w(int l, int r) {
int t = (r - l) / 2;
return (p[r] - p[r - t]) - (p[l + t] - p[l]);
}
void solve() {
deque<item> dq;
dq.push_back({1, n, 0});
for (int i = 1; i <= n; ++i) {
f[i] = k + f[dq.front().p] + w(dq.front().p, i);
++dq.front().l;
if (dq.front().l > dq.front().r) {
dq.pop_front();
}
while (!dq.empty()) {
auto [l, r, p] = dq.back();
if (f[i] + w(i, l) < f[p] + w(p, l)) {
dq.pop_back();
}
else break;
}
if (dq.empty()) {
dq.push_back({i + 1, n, i});
}
else {
auto& [l, r, p] = dq.back();
int low = l, high = r, pos = r + 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (f[i] + w(i, mid) < f[p] + w(p, mid)) {
pos = mid, high = mid - 1;
}
else {
low = mid + 1;
}
}
r = pos - 1;
if (pos <= n) {
dq.push_back({pos, n, i});
}
}
}
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
solve();
cout << f[n];
}
Ta sẽ chứng minh bằng cách phản chứng: giả sử tồn tại vị trí thỏa mãn . Để thuận tiện cho việc chứng minh, ta sẽ đặt (). Điều này tương đương với:
Trừ hai bất đẳng thức theo vế, ta được:
Tuy nhiên, theo tính chất của hàm , xét bộ số , ta có:
Điều này là vô lý. Vì vậy, ta có điều phải chứng minh.
Kĩ thuật này thường được sử dụng cùng với kĩ thuật Aliens' Trick, kĩ thuật từng xuất hiện trong đề thi IOI 2016. Ngoài ra, hầu hết các bài toán có thể giải bằng QHĐ bao lồi/QHĐ chia để trị đều có thể giải bằng kĩ thuật này.
Bạn đọc có thể luyện tập thêm về kĩ thuật ở những bài sau: