Aliens Trick (WQS Binary Search)
Mô tả nguyên lý
Kỹ thuật tìm kiếm nhị phân trên chi phí phạt (penalty) để giải các bài toán ràng buộc số lượng phần tử trong DP.
Cài đặt mẫu (Implementation)
// Chuyển đổi bài toán ràng buộc chính xác K phần tử thành bài toán tối ưu tự do với hệ số phạt.
Convex Hull Trick (CHT)
Mô tả nguyên lý
Tối ưu hóa các biểu thức quy hoạch động dạng tuyến tính $dp[i] = \min_j (m_j \cdot x_i + c_j)$.
Cài đặt mẫu (Implementation)
// Duy trì tập hợp các đường thẳng tạo thành bao lồi để tìm giá trị tối ưu cực nhanh.
Divide and Conquer DP Optimization
Mô tả nguyên lý
Tối ưu hóa độ phức tạp của các bài toán DP có dạng $dp[i][j] = \min_k (dp[i-1][k] + C[k][j])$.
Cài đặt mẫu (Implementation)
// Áp dụng chia để trị trên ma trận trạng thái để giảm một chiều tính toán từ $O(N^2)$ xuống $O(N \log N)$.
Knuth Optimization for DP
Mô tả nguyên lý
Tối ưu hóa các bài toán quy hoạch động khoảng cách thỏa mãn tính chất tứ giác (Quadrangle Inequality).
Cài đặt mẫu (Implementation)
// Giới hạn khoảng tìm kiếm điểm tối ưu k dựa trên tính chất đơn điệu của điểm cắt.
Monotone Queue DP Optimization
Mô tả nguyên lý
Tối ưu hóa các bài toán trượt cửa sổ trong quy hoạch động sử dụng hàng đợi đơn điệu.
Cài đặt mẫu (Implementation)
// Loại bỏ các phần tử kém tối ưu ra khỏi hàng đợi để luôn giữ phần tử tốt nhất ở đầu.
Slope Trick
Mô tả nguyên lý
Duy trì các hàm lồi bằng cách lưu trữ các điểm uốn (slope changes) qua hàng đợi ưu tiên.
Cài đặt mẫu (Implementation)
// Giải quyết các bài toán tối ưu hóa chi phí tuyệt đối với hàm chi phí lồi.