Thi đấu

Tối Ưu Quy Hoạch Động Bằng Bao Lồi (Convex Hull Trick)

Convex Hull Trick (CHT) là kỹ thuật hình học tối ưu hóa quy hoạch động cho phép tìm giá trị cực tiểu hoặc cực đại của tập hợp các đường thẳng tuyến tính trong thời gian O(log N) hoặc O(1).

Tối Ưu Quy Hoạch Động Bằng Bao Lồi (Convex Hull Trick)

Trong các bài toán quy hoạch động (Dynamic Programming - DP) nâng cao, việc thiết lập được công thức chuyển trạng thái thường chỉ mới hoàn thành một nửa chặng đường. Trở ngại lớn nhất là công thức đó có dạng phụ thuộc bậc hai:

\[dp[i] = \min_{j \lt i} \{ dp[j] + a[j] \cdot x[i] + b[j] \}\]

Nếu tính toán ngây thơ bằng hai vòng lặp lồng nhau, thuật toán sẽ tốn \(O(N^2)\) thời gian. Khi \(N = 10^5\), chương trình cần thực hiện khoảng \(10^{10}\) phép tính và nhận kết quả Time Limit Exceeded (TLE) ngay lập tức.

Tuy nhiên, nếu nhìn nhận biểu thức bên trong dưới con mắt hình học: Tại mỗi bước \(j\), ta có một đường thẳng \(L_j: y = m_j \cdot x + c_j\). Tại bước \(i\), ta cần tìm đường thẳng \(L_j\) có tung độ \(y\) nhỏ nhất tại hoành độ \(x = x[i]\). Kỹ thuật Convex Hull Trick (CHT - Tối ưu hóa bằng bao lồi) tận dụng hình dạng của bao lồi dưới (Lower Envelope) của các đường thẳng để đưa độ phức tạp từ \(O(N^2)\) xuống còn \(O(N \log N)\) hoặc thậm chí là \(O(N)\) tuyến tính!

TỐI ƯU QUY HOẠCH ĐỘNG BẰNG BAO LỒI (CONVEX HULL TRICK) Duy trì bao lồi dưới (Lower Envelope) các đường thẳng y = m*x + c để tìm giá trị nhỏ nhất Bao lồi dưới của các đường thẳng (Lower Envelope) x y L₁ L₂ L₃ x₁₂ x₂₃ Đường viền Cyan: Giá trị nhỏ nhất min(L_j(x)) tại mỗi x Điều kiện loại đường thẳng vô dụng GIAO ĐIỂM HAI ĐƯỜNG THẲNG: x(l1, l2) = (c1 - c2) / (m2 - m1) Đường l2 bị vô dụng khi x(l1, l2) ≥ x(l2, l3) NHÂN CHÉO SỐ NGUYÊN (__int128): (c2 - c1)*(m2 - m3) >= (c3 - c2)*(m1 - m2) Tránh hoàn toàn phép chia số thực double! Truy vấn x bất kỳ: Binary Search trong O(log N) HIỆU QUẢ TỐI ƯU HÓA: Quy hoạch động từ O(N²) giảm xuống O(N log N) hoặc O(N) với con trỏ hai đầu • Bộ nhớ O(N).
CONVEX HULL TRICK (CHT) Tối ưu quy hoạch động dạng min(m*x + c) Bao lồi dưới (Lower Envelope) Viền Cyan: Giá trị min(m_j * x + c_j) ĐIỀU KIỆN LOẠI ĐƯỜNG THẲNG L₂: intersect(L₁, L₂) ≥ intersect(L₂, L₃) (c₂ - c₁)*(m₂ - m₃) ≥ (c₃ - c₂)*(m₁ - m₂) Nhân chéo số nguyên 128-bit, 0 sai số! ĐỘ PHỨC TẠP TỐI ƯU: • Quy hoạch động: O(N²) → O(N log N) • Với x đơn điệu: Giảm tiếp còn O(N)
Mô hình bao lồi dưới (Lower Envelope) và điều kiện loại bỏ đường thẳng vô dụng bằng nhân chéo 128-bit.

Nhận diện dạng bài toán quy hoạch động tối ưu bằng CHT

Một công thức quy hoạch động có thể tối ưu bằng CHT khi thỏa mãn các đặc điểm sau:

  1. Trạng thái \(dp[i]\) chỉ phụ thuộc vào các trạng thái trước đó \(j \lt i\).
  2. Hàm chi phí chuyển trạng thái có dạng tuyến tính đối với biến truy vấn \(x[i]\): \[dp[i] = \min_{j \lt i} \{ m_j \cdot x[i] + c_j \}\] Trong đó:
  • \(x[i]\) là hoành độ truy vấn (chỉ phụ thuộc vào bước \(i\)).
  • \(m_j\) là hệ số góc (slope) của đường thẳng (chỉ phụ thuộc vào bước \(j\)).
  • \(c_j\) là hệ số tự do (intercept) của đường thẳng (thường chứa \(dp[j]\) và các đại lượng chỉ phụ thuộc vào \(j\)).

Phân loại các biến thể CHT

Tùy thuộc vào tính chất của dãy hệ số góc \(m_j\) và hoành độ truy vấn \(x[i]\), ta có các cách tiếp cận tối ưu:

Biến thể bài toán Tính chất hệ số góc \(m_j\) Tính chất hoành độ \(x[i]\) Cấu trúc dữ liệu tối ưu Thời gian mỗi truy vấn
Dạng 1 (Đơn điệu kép) Giảm dần đều Tăng dần đều Hàng đợi hai đầu (std::deque) \(O(1)\) amortized
Dạng 2 (Hệ số góc đơn điệu) Giảm dần đều Tùy ý (không sắp xếp) Ngăn xếp mảng động + Tìm kiếm nhị phân \(O(\log N)\)
Dạng 3 (Hoàn toàn tùy ý) Xuất hiện ngẫu nhiên Tùy ý Cây Li Chao hoặc Dynamic CHT \(O(\log N)\)

Bản chất hình học và điều kiện loại bỏ đường thẳng

Giả sử ta cần tìm giá trị nhỏ nhất (Min CHT) và các đường thẳng được thêm vào theo thứ tự hệ số góc giảm dần: \(m_1 \gt m_2 \gt m_3 \gt \dots\).

Khi vẽ các đường thẳng này trên mặt phẳng tọa độ \(Oxy\), giá trị nhỏ nhất tại mỗi hoành độ \(x\) được tạo thành từ các đoạn thẳng liên tiếp nối nhau. Đường bao tạo bởi các đoạn thẳng này có dạng lồi xuống dưới, gọi là Bao lồi dưới (Lower Envelope).

Khi nào một đường thẳng trở nên vô dụng?

Xét ba đường thẳng liên tiếp \(L_1, L_2, L_3\) với hệ số góc giảm dần: \(m_1 \gt m_2 \gt m_3\). Gọi hoành độ giao điểm giữa hai đường thẳng \(L_a\) và \(L_b\) là \(x(L_a, L_b)\): \[m_a \cdot x + c_a = m_b \cdot x + c_b \implies x(L_a, L_b) = \frac{c_b - c_a}{m_a - m_b}\]

Đường thẳng \(L_2\) sẽ hoàn toàn vô dụng (không bao giờ đóng góp vào giá trị nhỏ nhất tại bất kỳ hoành độ \(x\) nào) khi và chỉ khi giao điểm của nó với \(L_1\) nằm bên phải (hoặc trùng) giao điểm của \(L_1\) với \(L_3\): \[x(L_1, L_2) \ge x(L_2, L_3)\] Khi điều kiện này xảy ra, đường thẳng \(L_2\) bị "che khuất" hoàn toàn bởi \(L_1\) và \(L_3\). Ta có thể loại bỏ \(L_2\) vĩnh viễn khỏi bao lồi mà không làm ảnh hưởng đến kết quả của bất kỳ truy vấn nào trong tương lai.

Xử lý trường hợp đường thẳng song song

Nếu đường thẳng mới thêm vào có cùng hệ số góc với đường thẳng trên đỉnh ngăn xếp (\(m_{\text{new}} = m_{\text{top}}\)):

  • Hai đường thẳng này song song với nhau và không bao giờ cắt nhau.
  • Đối với bài toán tìm giá trị nhỏ nhất, đường thẳng có hệ số tự do \(c\) nhỏ hơn sẽ luôn nằm dưới đường thẳng kia tại mọi hoành độ \(x\).
  • Do đó, nếu \(c_{\text{new}} \lt c_{\text{top}}\), ta loại bỏ đường thẳng trên đỉnh ngăn xếp và thay thế bằng đường thẳng mới. Ngược lại nếu \(c_{\text{new}} \ge c_{\text{top}}\), ta bỏ qua đường thẳng mới vì nó không bao giờ tối ưu hơn.

Kỹ thuật nhân chéo 128-bit chống sai số số thực

Biểu thức kiểm tra loại bỏ đường thẳng: \[\frac{c_2 - c_1}{m_1 - m_2} \ge \frac{c_3 - c_2}{m_2 - m_3}\] Vì các hệ số góc giảm dần nên \(m_1 - m_2 \gt 0\) và \(m_2 - m_3 \gt 0\). Ta có thể nhân chéo hai vế để tránh hoàn toàn phép chia số thực: \[(c_2 - c_1) \cdot (m_2 - m_3) \ge (c_3 - c_2) \cdot (m_1 - m_2)\]

Trong lập trình thi đấu, giá trị \(c\) có thể lên tới \(10^{18}\) và \(m\) có thể lên tới \(10^9\). Phép nhân hai đại lượng này có thể đạt tới \(10^{27}\), vượt quá giới hạn của số nguyên 64-bit long long (\(2^{63} - 1 \approx 9 \cdot 10^{18}\)). Để ngăn chặn hoàn toàn lỗi tràn số nguy hiểm này, ta sử dụng kiểu số nguyên 128-bit __int128_t trong C++ khi thực hiện phép nhân chéo.

Thuật toán truy vấn bằng tìm kiếm nhị phân

Khi hoành độ truy vấn \(x\) không đơn điệu tăng dần, ta không thể dùng con trỏ trượt hai đầu. Tuy nhiên, nhờ tính chất lồi của bao lồi dưới, hàm giá trị \(y(x) = m_k \cdot x + c_k\) đối với chỉ số đường thẳng \(k\) trên bao lồi là một hàm đơn đỉnh (unimodal).

Ta có thể áp dụng tìm kiếm nhị phân trên tập hợp các đường thẳng đang lưu trong ngăn xếp:

  1. Đặt khoảng tìm kiếm ban đầu \(l = 0, r = K - 1\) (với \(K\) là số lượng đường thẳng hiện có trên bao lồi).
  2. Tại mỗi bước, xét trung điểm \(mid = (l + r) / 2\).
  3. So sánh giá trị của hai đường thẳng liền kề tại hoành độ truy vấn \(x\):
    • Tính \(v_1 = m[mid] \cdot x + c[mid]\).
    • Tính \(v_2 = m[mid + 1] \cdot x + c[mid + 1]\).
    • Nếu \(v_1 \gt v_2\): Đường thẳng \(mid + 1\) cho giá trị tốt hơn, nghiệm tối ưu chắc chắn nằm từ \(mid + 1\) về phía bên phải. Ta thu hẹp khoảng tìm kiếm: \(l = mid + 1\).
    • Nếu \(v_1 \le v_2\): Đường thẳng \(mid\) cho giá trị tốt hơn hoặc bằng, nghiệm tối ưu nằm từ \(mid\) về phía bên trái. Ta thu hẹp khoảng tìm kiếm: \(r = mid\).
  4. Khi khoảng tìm kiếm thu hẹp về một phần tử duy nhất (\(l = r\)), đường thẳng \(l\) chính là đường thẳng tối ưu nhất, trả về giá trị \(m[l] \cdot x + c[l]\).

Mỗi lần truy vấn chỉ tốn đúng \(O(\log K) \le O(\log N)\) phép tính, đáp ứng hoàn hảo giới hạn thời gian thi đấu.

Học cùng giảng viên

Chủ đề này nằm trong Buổi 14 - Geometry cơ bản + Convex Hull của Tài năng lập trình. Xem đề cương

Cài đặt chuẩn C++17 và Python 3

Dưới đây là lời giải mẫu hoàn chỉnh của cấu trúc Convex Hull Trick, sử dụng mảng động kết hợp tìm kiếm nhị phân và nhân chéo 128-bit chống tràn số:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Cấu trúc Convex Hull Trick (CHT) tìm giá trị nhỏ nhất min(m * x + c)
// Yêu cầu: Hệ số góc m không tăng khi thêm vào (hai đường cùng hệ số góc thì chỉ giữ đường thấp hơn)
// Hỗ trợ truy vấn với hoành độ x bất kỳ bằng tìm kiếm nhị phân trong O(log N)
struct ConvexHullTrick {
    vector<long long> m, c;

    // Kiểm tra xem đường thẳng l2 có bị l1 và l3 bao bọc (trở nên vô dụng) không
    // Giao điểm x(l1, l2) >= x(l2, l3)
    // Tương đương: (c2 - c1) * (m2 - m3) >= (c3 - c2) * (m1 - m2)
    bool bad(int l1, int l2, int l3) {
        __int128 c1 = c[l1], m1 = m[l1];
        __int128 c2 = c[l2], m2 = m[l2];
        __int128 c3 = c[l3], m3 = m[l3];
        return (c2 - c1) * (m2 - m3) >= (c3 - c2) * (m1 - m2);
    }

    void add(long long slope, long long intercept) {
        // Đường song song với đường trên đỉnh: chỉ giữ đường có hệ số tự do nhỏ hơn
        if (!m.empty() && m.back() == slope) {
            if (c.back() <= intercept) return;
            m.pop_back();
            c.pop_back();
        }
        m.push_back(slope);
        c.push_back(intercept);
        while (m.size() >= 3 && bad(m.size() - 3, m.size() - 2, m.size() - 1)) {
            m.erase(m.end() - 2);
            c.erase(c.end() - 2);
        }
    }

    long long eval(int idx, long long x) {
        return m[idx] * x + c[idx];
    }

    long long query(long long x) {
        int l = 0, r = (int)m.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (eval(mid, x) > eval(mid + 1, x)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return eval(l, x);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    vector<long long> dp(n + 1, 0);
    ConvexHullTrick cht;

    // dp[1] = 0
    cht.add(b[1], dp[1]);

    for (int i = 2; i <= n; i++) {
        dp[i] = cht.query(a[i]);
        cht.add(b[i], dp[i]);
    }

    cout << dp[n] << "\n";

    return 0;
}

Đánh giá độ phức tạp thuật toán

  • Thời gian thêm đường thẳng: Mỗi đường thẳng được đẩy vào mảng đúng một lần và bị loại bỏ tối đa một lần trong suốt quá trình chạy. Tổng thời gian cho \(N\) thao tác thêm đường thẳng là \(O(N)\) amortized.
  • Thời gian thực hiện truy vấn: Mỗi bước truy vấn thực hiện một lần tìm kiếm nhị phân trên mảng đường thẳng có kích thước tối đa \(N\), mất \(O(\log N)\). Tổng thời gian cho \(N\) truy vấn là \(O(N \log N)\).
  • Tổng thời gian toàn bộ thuật toán: \[O(N \log N)\] Nếu hoành độ truy vấn \(x[i]\) cũng đơn điệu tăng dần, ta có thể dùng con trỏ trượt hai đầu (Two Pointers) để tìm kiếm trong \(O(1)\) amortized, đưa tổng thời gian chạy về mức \(O(N)\) tuyến tính!
  • Bộ nhớ (Space Complexity): Mảng lưu trữ tối đa \(N\) đường thẳng chiếm \(O(N)\) bộ nhớ.

Luyện ngay trên Big-O Coding

Để nắm vững kỹ thuật tối ưu hóa quy hoạch động bằng bao lồi CHT, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:

Nếu hệ số góc m không giảm dần mà xuất hiện ngẫu nhiên thì làm sao?

Khi hệ số góc \(m\) không đơn điệu, bạn không thể thêm đường thẳng vào cuối ngăn xếp một cách đơn giản. Lúc này, có hai giải pháp mạnh mẽ:

  1. Cây Li Chao (Li Chao Tree): Một cấu trúc Segment Tree quản lý các đoạn thẳng, cho phép thêm đường thẳng bất kỳ và truy vấn giá trị cực trị trong thời gian \(O(\log(\mathrm{range\_X}))\). Cài đặt rất gọn và không sợ tràn số giao điểm.
  2. Dynamic CHT (sử dụng std::set): Quản lý tập hợp đường thẳng theo hệ số góc và tìm kiếm giao điểm động bằng hàm std::set::lower_bound.
CHT tìm giá trị lớn nhất (Max Envelope) khác gì so với giá trị nhỏ nhất?

Bao lồi trên (Upper Envelope) tìm cực đại \(\max(m x + c)\) có nguyên lý hoàn toàn đối xứng:

  • Hệ số góc \(m\) được thêm theo thứ tự tăng dần.
  • Điều kiện loại bỏ đường thẳng giữ nguyên dạng: \(L_2\) vô dụng khi \(x(L_1, L_2) \ge x(L_2, L_3)\) (hệ số góc tăng dần thì \(L_1\) cao nhất ở phía trái, \(L_3\) cao nhất ở phía phải, giống hệt bao lồi dưới).
  • Hoặc một mẹo đơn giản trong thi đấu: Đổi dấu hệ số \((-m, -c)\) để đưa bài toán tìm Max về tìm Min quen thuộc!
Khi nào nên dùng CHT và khi nào nên dùng Chia để trị DP (Divide and Conquer DP)?
  • Dùng CHT: Khi hàm chi phí có dạng tích trực tiếp giữa trạng thái cũ và trạng thái mới (\(m_j \cdot x_i\)), bất kể bài toán có phân hoạch \(K\) đoạn hay không.
  • Dùng Chia để trị DP: Khi hàm chi phí thỏa mãn điều kiện tứ giác (Quadrangle Inequality) và bài toán có dạng phân hoạch thành đúng \(K\) đoạn.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483