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

Slope Trick

huunguyen Updated Tháng sáu 1, 2026

Slope Trick là kỹ thuật tối ưu quy hoạch động khi hàm DP là một hàm lồi, từng đoạn tuyến tính (piecewise linear convex function). Thay vì lưu toàn bộ hàm $f (x)$ (vô hạn giá trị hoặc tới $O (N)$ điểm), ta chỉ lưu các điểm gãy của đạo hàm (slope) bằng một vài heap. Mỗi bước chuyển DP trở thành một thao tác đẩy/lấy phần tử trên heap, đưa độ phức tạp từ $O (N^{2})$ (hoặc tệ hơn) xuống $O (N \log N)$ .

Bài toán mẫu kinh điển: cho dãy $a [1 . . N]$ , tìm dãy $b [1 . . N]$ không giảm sao cho $\sum_{i} | a_{i} - b_{i} |$ nhỏ nhất. DP ngây thơ là $d p [i] [v] = {min}_{u \leq v} d p [i - 1] [u] + | a_{i} - v |$ với $v$ chạy trên toàn miền giá trị — chậm. Slope Trick giải trong $O (N \log N)$ .

Ý tưởng / Trực giác

Tại sao hàm DP lại lồi? Nhiều bài DP có dạng

$d p_{i} (v) = (phép biến đổi lồi của d p_{i - 1}) + | v - a_{i} | .$

Hai sự thật giúp kỹ thuật hoạt động:

Tổng các hàm lồi là hàm lồi. $| v - a_{i} |$ lồi; cộng dồn vẫn lồi.
Phép "prefix-min" $g (v) = {min}_{u \leq v} f (u)$ (cần thiết để ép $b$ không giảm) giữ nguyên tính lồi: nó chỉ "san phẳng" phần dốc lên bên trái của đáy thành nằm ngang.

Một hàm lồi từng đoạn tuyến tính được mô tả đầy đủ bởi:

giá trị nhỏ nhất $minF$ ,
và đa tập các điểm gãy (nơi độ dốc tăng thêm 1 đơn vị).

Trực giác hình học: đi từ trái sang phải, độ dốc của $f$ tăng dần (vì lồi). Mỗi điểm gãy là một vị trí $x$ mà độ dốc tăng. Ta chia điểm gãy làm hai nhóm quanh đáy phẳng (nơi slope $= 0$ ):

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

Bất biến: mọi phần tử trong L $\leq$ mọi phần tử trong R, và $f$ đạt min, phẳng (slope $= 0$ ) trên đoạn $[L . top (), R . top ()]$ .

Phép thêm $| x - a |$ chính là chèn điểm gãy tại $a$ vào cả hai phía rồi sửa lại bất biến. Đẩy $a$ vào L và vào R; nếu đỉnh của L vượt qua đỉnh của R thì hai bên "chồng lấn" — ta hoán đổi chúng và cộng phần chênh lệch vào $minF$ (vì đáy đã bị nâng lên đúng bằng khoảng cách đó).

Ví dụ chạy tay

Bài: dãy không giảm, $a = [3, 1, 4, 1]$ , tối thiểu $\sum | a_{i} - b_{i} |$ . Với ràng buộc không giảm ta dùng một max-heap L: mỗi bước đẩy $a_{i}$ vào hai lần (tương đương thêm $| x - a_{i} |$ rồi prefix-min), nếu đỉnh vượt $a_{i}$ thì kéo đỉnh xuống $a_{i}$ và cộng chênh lệch vào đáp số.

Quy ước: L vẽ từ lớn → nhỏ, đỉnh (max) đánh dấu ^. cost là $minF$ tích luỹ.

i=1, a=3:  push 3, push 3
   L = [ 3  3 ]
         ^
   top=3 không > 3  -> cost += 0
   cost = 0

i=2, a=1:  push 1, push 1
   L = [ 3  3  1  1 ]
         ^                 đỉnh = 3 > a=1
   kéo đỉnh xuống: pop 3, push 1, cost += (3-1)=2
   L = [ 3  1  1  1 ]
         ^
   cost = 2          (nghĩa: b tốt nhất tới đây ép b2 = 1, nhưng b1>=... bù chi phí 2)

i=3, a=4:  push 4, push 4
   L = [ 4  4  3  1  1  1 ]
         ^                 đỉnh = 4 không > a=4
   cost += 0
   cost = 2

i=4, a=1:  push 1, push 1
   L = [ 4  4  3  1  1  1  1  1 ]
         ^                 đỉnh = 4 > a=1
   pop 4, push 1, cost += (4-1)=3
   L = [ 4  3  1  1  1  1  1  1 ]
         ^
   cost = 5

Đáp số $= 5$ . Kiểm chứng tay: chọn $b = [3, 3, 4, 4]$ cho $| 3 - 3 | + | 1 - 3 | + | 4 - 4 | + | 1 - 4 | = 0 + 2 + 0 + 3 = 5$ . Khớp.

Đỉnh heap luôn cho biết giá trị tối ưu cuối cùng của $b_{N}$ (ở đây $b_{N}$ có thể $= 4$ ), và cost cộng dồn đúng phần "phải nâng lên" do ràng buộc không giảm.

Cài đặt

Hai heap tổng quát — thêm $| x - a |$

Dùng khi cần cả hai nhánh (vd hàm có cả ràng buộc trái và phải):

#include <bits/stdc++.h>
using namespace std;

// L: max-heap các điểm gãy bên trái đáy
// R: min-heap các điểm gãy bên phải đáy
// minF: giá trị nhỏ nhất hiện tại của f
priority_queue<long long> L;
priority_queue<long long, vector<long long>, greater<long long>> R;
long long minF = 0;

// f(x) += |x - a|
void add_abs(long long a) {
    L.push(a);
    R.push(a);
    // Nếu hai bên chồng lấn (đỉnh trái vượt đỉnh phải) thì hoán đổi,
    // phần chênh lệch chính là lượng đáy bị nâng lên.
    if (L.top() > R.top()) {
        long long l = L.top(); L.pop();
        long long r = R.top(); R.pop();
        minF += l - r;          // cộng vào giá trị nhỏ nhất
        L.push(r);
        R.push(l);
    }
}

Bản rút gọn cho dãy không giảm (chỉ một heap)

Ràng buộc không giảm = prefix-min = "xoá" nhánh phải, nên chỉ cần L:

// Tối thiểu sum |a[i] - b[i]| với b[] không giảm. Trả về chi phí.
long long min_cost_nondecreasing(const vector<long long>& a) {
    priority_queue<long long> L;   // max-heap các điểm gãy
    long long cost = 0;            // = minF
    for (long long x : a) {
        L.push(x);
        L.push(x);                 // thêm |.-x| rồi prefix-min ~ đẩy 2 lần
        long long top = L.top(); L.pop();
        cost += top - x;           // top >= x luôn đúng nhờ bất biến
    }
    return cost;
}

Lưu ý vì sao chỉ đẩy hai lần: thêm $| x - a |$ tạo hai điểm gãy tại $a$ ; phép prefix-min loại bỏ ngay điểm gãy bên phải, nên hiệu ứng ròng lên L là chèn $a$ rồi (nếu đỉnh vượt $a$ ) kéo đỉnh xuống.

Lazy offset cho phép dịch

Khi ràng buộc là $l \leq b_{i} - b_{i - 1} \leq r$ (thay vì chỉ $\geq 0$ ), trước khi xử lý $a_{i}$ ta phải dịch nhánh trái sang trái $l$ và nhánh phải sang phải $r$ . Dịch cả heap tốn kém, nên dùng biến offset cộng dồn (lazy):

long long addL = 0, addR = 0;     // offset lười cho L và R
// đọc giá trị thực: L.top() + addL ; R.top() + addR
// dịch: addL -= l;  addR += r;    (O(1) mỗi bước)

Độ phức tạp

Thời gian: $O (N \log N)$ . Mỗi phần tử của dãy gây ra một số hữu hạn (hằng số) thao tác push/pop trên heap, mỗi thao tác $O (\log N)$ . Tổng số điểm gãy không vượt quá $O (N)$ nên kích thước heap luôn $\leq O (N)$ .
Bộ nhớ: $O (N)$ — lưu các điểm gãy trong heap; tối đa $O (N)$ điểm gãy vì mỗi bước thêm hằng số điểm gãy.

So với DP ngây thơ $d p [i] [v]$ tốn $O (N \cdot V)$ thời gian và bộ nhớ ( $V$ = miền giá trị, có thể tới $10^{9}$ ), Slope Trick độc lập hoàn toàn với $V$ .

⚠️ Lỗi thường gặp

Tràn số. minF và chi phí cộng dồn các hiệu $l - r$ có thể lên tới $N \times max | a_{i} |$ , dễ vượt int. Luôn dùng long long cho heap, offset và đáp số. Triệu chứng: kết quả âm hoặc nhỏ bất thường khi $N$ lớn.
Quên kiểm tra heap rỗng. Truy cập L.top() / R.top() khi heap rỗng là hành vi không xác định (thường crash hoặc rác). Ở bước đầu tiên R rỗng — phải if (!R.empty() && L.top() > R.top()). Triệu chứng: RE/WT ở test nhỏ.
Áp dụng khi hàm KHÔNG lồi. Slope Trick chỉ đúng nếu mọi phép chuyển bảo toàn tính lồi từng đoạn tuyến tính. Nếu chi phí là $| a_{i} - b_{i} |^{2}$ , hay có nhân/chia làm gãy tuyến tính, hàm vẫn lồi nhưng không còn từng đoạn tuyến tính — heap điểm gãy không mô hình hoá được. Kiểm tra điều kiện trước khi dùng.
Sai chiều prefix-min vs suffix-min. Ràng buộc không giảm ( $b_{i} \geq b_{i - 1}$ ) cho prefix-min → giữ nhánh trái L. Ràng buộc không tăng ( $b_{i} \leq b_{i - 1}$ ) cho suffix-min → giữ nhánh phải R. Nhầm chiều cho đáp án của bài đối ngẫu. Mẹo: với "không tăng" hãy đổi dấu/đảo dãy rồi quay về "không giảm".
Đẩy thiếu/thừa số lần. Trong bản một-heap, mỗi phần tử phải push đúng hai lần. Đẩy một lần làm hàm không tăng đủ độ dốc (sai chi phí); đẩy ba lần làm dốc gấp đôi. Triệu chứng: lệch hệ số chi phí.
Lazy offset cộng nhầm bên. Khi dùng offset lười, mọi lần top()/push()/pop() phải quy đổi qua đúng offset của heap tương ứng (addL cho L, addR cho R). Trộn lẫn hai offset là lỗi rất khó tìm; nên bọc trong hàm topL(), pushL().

Biến thể / Mở rộng

DP trên cây bằng Slope Trick: gộp các hàm lồi của con bằng cách hợp nhất (merge) các heap; dùng small-to-large hoặc leftist/skew heap để hợp nhất trong $O (\log N)$ khấu hao.
Liên hệ kỹ thuật khác: khi hàm DP là lồi nhưng không từng đoạn tuyến tính (vd bậc hai), dùng Convex Hull Trick hoặc Li Chao Tree thay thế. Xem thêm Quy hoạch động.
Aliens trick (Lagrangian): bài "chọn đúng $K$ phần/đặt đúng $K$ điểm" thường kết hợp Slope Trick/convex DP với tham số hoá Lagrange để bỏ ràng buộc đếm $K$ .

Bài tập luyện

Nhà kính của Sprout (greenhouse) — (Expert) Đặt đúng $K$ điểm trên đường thẳng tối thiểu $\sum | x_{i} - g |$ (k-median 1 chiều); luyện hàm chi phí $| x - g |$ lồi từng đoạn, kết hợp tham số $K$ .
Cải tạo vườn hoa (landscape) — (Expert) DP với chi phí mua/bỏ/chuyển đất theo $| i - j |$ ; mô hình Slope Trick hai nhánh kèm dịch hàm (shift) qua từng luống.
Cắt Cỏ Nghịch Ngợm (mowmis) — (Master) Tối thiểu diện tích cỏ bị cắt trên dãy con tăng; DP lồi cần Slope Trick + sweep, mức nâng cao tổng hợp.