Slope Trick

Wiki › Thuật toán › Quy hoạch động (DP)

huunguyen · Last updated 8, Tháng 4, 2026, 15:34

Slope Trick là kỹ thuật DP xử lý các hàm lồi từng đoạn tuyến tính (piecewise linear convex function) hiệu quả bằng cách lưu các điểm gãy của đạo hàm thay vì toàn bộ hàm.

Ý tưởng: Hàm $f (x)$ lồi từng đoạn có dạng $\sum c_{i} max (0, x - a_{i})$ — hoàn toàn xác định bởi tập điểm gãy. Các phép biến đổi thường gặp trong DP tương ứng với các thao tác đơn giản trên tập điểm gãy.

Ứng dụng: Các bài DP liên quan đến chi phí $| a_{i} - b_{i} |$ (L1 distance), chỉnh sửa dãy số, isotonic regression.

Biểu diễn

Lưu hàm $f$ lồi bằng multiset các điểm gãy đạo hàm:

L: max-heap (priority_queue) — các điểm gãy phía trái (nơi slope tăng từ âm lên 0).
R: min-heap — các điểm gãy phía phải (nơi slope tăng từ 0 lên dương).

Bất biến: L.top() <= R.top() và slope = 0 trên đoạn $[L.top(), R.top()]$ .

Các phép biến đổi cơ bản

// f(x) → f(x) + |x - a| (thêm chi phí khoảng cách đến a)
// Tương đương: thêm điểm gãy a vào cả L và R, điều chỉnh

long long add_abs(priority_queue<long long>& L,
                  priority_queue<long long, vector<long long>, greater<long long>>& R,
                  long long a) {
    long long cost = 0;

    L.push(a);
    // Điều chỉnh: nếu L.top() > R.top(), cần đẩy xuống
    if (!R.empty() && L.top() > R.top()) {
        long long l = L.top(); L.pop();
        long long r = R.top(); R.pop();
        cost += l - r;
        L.push(r);
        R.push(l);
    }
    R.push(a);
    if (!L.empty() && L.top() > R.top()) {
        long long l = L.top(); L.pop();
        long long r = R.top(); R.pop();
        cost += l - r;
        L.push(r);
        R.push(l);
    }

    return cost;
}

Ví dụ: Minimum Cost to Make Array Non-Decreasing

Cho mảng $a [1 . . n]$ , tìm dãy $b [1 . . n]$ không giảm sao cho $\sum | a_{i} - b_{i} |$ nhỏ nhất.

// dp[i][v] = chi phí nhỏ nhất để làm b[1..i] không giảm với b[i] = v
// dp[i][v] = min_{u <= v} dp[i-1][u] + |a[i] - v|

// Slope Trick: dp[i] là hàm lồi của v
// Thao tác "prefix min" tương đương mở rộng nửa trái hàm đến -∞

long long min_cost_nondecreasing(vector<long long>& a) {
    int n = a.size();
    priority_queue<long long> L;   // max-heap
    long long cost = 0;

    for (int i = 0; i < n; i++) {
        L.push(a[i]);
        L.push(a[i]);
        long long top = L.top(); L.pop();
        cost += max(0LL, top - a[i]);
        // Sau thao tác prefix-min: chỉ cần giữ L (R = +∞)
    }
    return cost;
}

Ví dụ: Isotonic Regression (L1)

// Dãy b[] không giảm minimize sum |a[i] - b[i]|
// Dùng slope trick với chỉ max-heap L
priority_queue<long long> pq;
long long ans = 0;

for (long long x : a) {
    pq.push(x);
    if (pq.top() > x) {
        ans += pq.top() - x;
        pq.pop();
        pq.push(x);
    }
}

Phép dịch chuyển (Shift)

Khi DP cần dịch toàn bộ hàm: $f (x) \to f (x - c)$ (dịch phải $c$ ) hoặc mở rộng đáy (add $max (0, l - x) + max (0, x - r)$ type constraints):

// Dịch tất cả điểm gãy trong L sang phải c: thêm offset
long long offset_L = 0, offset_R = 0;

// Thay vì dịch thực sự, lưu offset
// Khi push/pop: cộng/trừ offset

Độ phức tạp

$O (N \log N)$ — mỗi phần tử thêm $O (\log N)$ vào heap.

Khi nào dùng Slope Trick?

DP với công thức chuyển $f (v) \to {min}_{u \leq v} (g (u)) + h (v)$ (isotonic-type).
Chi phí $| a_{i} - b_{i} |$ hoặc $max (0, a_{i} - b_{i})$ .
Bài toán scheduling, làm mượt dãy số (L1 smoothing).
Khi hàm DP là lồi từng đoạn tuyến tính và cần tránh $O (N^{2})$ .

Bình luận

Không có bình luận tại thời điểm này.