Bài 45: Tối ưu quy hoạch động trong C++ và Python: min tiền tố, hàng đợi đơn điệu, Convex Hull Trick, Li Chao tree, chia để trị tối ưu
Lời mở đầu
Ở bài 19 và bài 27 em đã quen việc đặt trạng thái và viết công thức truy hồi. Nhưng ở đề HSG quốc gia, viết được công thức mới là một nửa bài: rất nhiều công thức có dạng $dp_i = \min_{j < i} \big(dp_j + \text{cost}(j, i)\big)$, có $n$ trạng thái, mỗi trạng thái duyệt $n$ lựa chọn, tổng $O(n^2)$, với $n = 2 \cdot 10^5$ là quá chậm. Nửa còn lại của bài là tối ưu phép lấy min ấy.
Em đã gặp một lần rồi: bài toán nhảy ô ở bài 25 dùng hàng đợi đơn điệu để lấy max trên cửa sổ trượt. Hôm nay ta hệ thống lại thành một bộ công cụ: min tiền tố, deque đơn điệu, Convex Hull Trick (biến mỗi $j$ thành một đường thẳng), Li Chao tree (cây phân đoạn của bài 31 chứa đường thẳng), và chia để trị tối ưu (dùng tính đơn điệu của điểm tối ưu, nối tiếp tư duy chia để trị ở bài 24).
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Nhận dạng QHĐ cần tối ưu, tối ưu bằng min tiền tố
Hầu hết các bài trong bài học này có chung một dáng:
$dp_i = \min_{j \in J(i)} \big( dp_j + \text{cost}(j, i) \big)$
trong đó $J(i)$ là tập các trạng thái trước mà $i$ được phép đi từ đó. Tính thẳng tốn $\sum |J(i)|$, thường là $O(n^2)$. Trước khi nghĩ tới kỹ thuật cao siêu, em hãy tự hỏi hai câu:
- $J(i)$ trông như thế nào? Mọi $j < i$ (một tiền tố), hay $k$ ô ngay trước (cửa sổ trượt), hay một cửa sổ lệch $[i - R, i - L]$?
- $\text{cost}(j, i)$ có tách được không? Nếu $\text{cost}(j, i) = f(i) + g(j)$ thì $f(i)$ ra ngoài dấu min, bên trong chỉ còn $dp_j + g(j)$, không phụ thuộc $i$ nữa.
Hình 1. Ba dạng tập $J(i)$ hay gặp (ô xanh dương là $i$, ô vàng là các $j$ được dùng). Tập là tiền tố thì giữ min tiền tố; tập là cửa sổ có hai đầu cùng tiến thì dùng deque đơn điệu.
Tách biến + min tiền tố. Ví dụ $dp_i = \min_{j < i} \big(dp_j + a_i - b_j\big)$. Viết lại $dp_i = a_i + \min_{j < i}(dp_j - b_j)$. Đại lượng trong ngoặc không phụ thuộc $i$, nên chỉ cần một biến best lưu min của $dp_j - b_j$ đã gặp: tính xong $dp_i$ thì cập nhật best. Từ $O(n^2)$ còn $O(n)$. Đây là kỹ thuật đơn giản nhất nhưng gặp cực nhiều, nhất là trong QHĐ hai chiều, nơi chiều thứ hai đóng vai “tiền tố”.
Bài toán. Cho dãy $a_1, \ldots, a_n$ ($n \le 5000$, $1 \le a_i \le 100$). Hãy chọn dãy không giảm $b_1 \le b_2 \le \ldots \le b_n$ với $1 \le b_i \le 100$ sao cho $\sum |a_i - b_i|$ nhỏ nhất.
Gọi $dp[i][v]$ là chi phí nhỏ nhất cho $i$ phần tử đầu khi $b_i = v$. Phần tử trước phải có $b_{i-1} = u \le v$, nên
$dp[i][v] = |a_i - v| + \min_{u \le v} dp[i-1][u].$
Tính thẳng: $n \cdot 100 \cdot 100 = 5 \cdot 10^7$, vẫn chạy nhưng nếu giá trị lên $10^3$ thì hỏng. Nhận ra $\min_{u \le v}$ là min tiền tố của hàng $i - 1$: duyệt $v$ tăng dần và giữ biến best. Mỗi hàng còn $O(V)$, tổng $O(nV)$.
| v = 1 | v = 2 | v = 3 | v = 4 | v = 5 | |
|---|---|---|---|---|---|
| $a_1 = 3$ | 2 | 1 | 0 | 1 | 2 |
| min tiền tố | 2 | 1 | 0 | 0 | 0 |
| $a_2 = 1$ | 2 | 2 | 2 | 3 | 4 |
| min tiền tố | 2 | 2 | 2 | 2 | 2 |
| $a_3 = 2$ | 3 | 2 | 3 | 4 | 5 |
Bảng 1. Ba hàng đầu với $a = [3, 1, 2, \ldots]$ (chỉ vẽ $v \le 5$). Mỗi ô của hàng mới = $|a_i - v|$ + ô cùng cột ở dòng “min tiền tố” ngay trên. Ví dụ $dp[3][2] = |2 - 2| + 2 = 2$.
Xem code C++ / Python: dãy không giảm chi phí nhỏ nhất với min tiền tố (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
const int V = 100;
int n;
cin >> n;
vector<long long> dp(V + 1, 0), nd(V + 1); // dp[v]: hàng i - 1, b[i-1] = v
for(int i = 0; i < n; i++){
int a;
cin >> a;
long long best = LLONG_MAX; // min tiền tố dp[1..v]
for(int v = 1; v <= V; v++){
best = min(best, dp[v]);
nd[v] = best + abs(a - v);
}
dp = nd;
}
cout << *min_element(dp.begin() + 1, dp.end());
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
V = 100
dp = [0] * (V + 1) # dp[v]: hàng i - 1, b[i-1] = v
for i in range(n):
a = int(data[1 + i])
nd = [0] * (V + 1)
best = float('inf') # min tiền tố dp[1..v]
for v in range(1, V + 1):
if dp[v] < best:
best = dp[v]
nd[v] = best + abs(a - v)
dp = nd
print(min(dp[1:]))
main()Phần 2QHĐ + hàng đợi đơn điệu: khi j chạy trong cửa sổ trượt
Bài toán đặt camera. Hàng rào có $n$ vị trí, đặt camera ở vị trí $i$ tốn $c_i$ ($n \le 10^6$). Yêu cầu: mọi đoạn $k$ vị trí liên tiếp có ít nhất một camera. Tổng chi phí nhỏ nhất là bao nhiêu?
Gọi $dp_i$ là chi phí nhỏ nhất khi đặt camera tại $i$ và mọi yêu cầu bên trái $i$ đã được thoả. Camera ngay trước đó ở $j$ thì giữa $j$ và $i$ có $i - j - 1$ ô trống, phải $\le k - 1$, tức $j \ge i - k$. Thêm vị trí gốc $0$ ($dp_0 = 0$) và vị trí đích $n + 1$ (chi phí $0$) để khỏi xét riêng hai đầu:
$dp_i = c_i + \min_{i - k \le j \le i - 1} dp_j, \qquad \text{đáp án} = dp_{n+1}.$
Tập $j$ là cửa sổ độ dài $k$ trượt sang phải mỗi khi $i$ tăng: đúng tình huống của hàng đợi đơn điệu ở bài 25. Deque lưu các chỉ số $j$ có $dp_j$ tăng dần từ đầu tới cuối. Với mỗi $i$: (1) bỏ ở đầu các chỉ số $< i - k$; (2) đầu deque là min, tính $dp_i$; (3) bỏ ở cuối các chỉ số có $dp \ge dp_i$ rồi đẩy $i$ vào cuối. Một chỉ số bị bỏ ở cuối vì nó cũ hơn $i$ (rời cửa sổ sớm hơn) mà lại không tốt hơn: nó vĩnh viễn hết cơ hội.
Bảng thì khó thấy deque “sống” thế nào. Em bấm Tiếp để xem từng bước: cửa sổ (ô vàng) trượt, đầu deque (xanh lá) luôn là min, và những ô đỏ bị loại vĩnh viễn. Thử đổi $k$ hoặc nhập dãy giảm dần để thấy deque dài ra:
Xem code C++ / Python: qhd đặt camera với deque đơn điệu (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> c(n + 2, 0), dp(n + 2, 0);
for(int i = 1; i <= n; i++) cin >> c[i];
deque<int> dq;
dq.push_back(0); // gốc 0: dp[0] = 0
for(int i = 1; i <= n + 1; i++){ // ô n + 1 là đích, c = 0
while(dq.front() < i - k) dq.pop_front(); // ra khỏi cửa sổ [i-k, i-1]
dp[i] = c[i] + dp[dq.front()]; // đầu deque là min
while(!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
dq.push_back(i);
}
cout << dp[n + 1];
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
c = [0] + [int(x) for x in data[2:2 + n]] + [0] # ô n + 1 là đích
dp = [0] * (n + 2)
dq = deque([0]) # gốc 0: dp[0] = 0
for i in range(1, n + 2):
while dq[0] < i - k: # ra khỏi cửa sổ
dq.popleft()
dp[i] = c[i] + dp[dq[0]] # đầu deque là min
while dq and dp[dq[-1]] >= dp[i]:
dq.pop()
dq.append(i)
print(dp[n + 1])
main()Cửa sổ lệch $[i - R, i - L]$. Nhiều bài có cả khoảng cách tối thiểu: ví dụ ếch nhảy mỗi bước từ $L$ tới $R$ ô. Khi đó $j = i - 1, \ldots, i - L + 1$ chưa được phép dùng. Cách làm: chỉ đẩy $j = i - L$ vào deque ngay trước khi tính $dp_i$ (đẩy “trễ” $L$ bước), còn việc bỏ đầu thì so với $i - R$. Thứ tự mỗi bước: đẩy $i - L$ → bỏ đầu $< i - R$ → đọc đầu deque. Bài tập 3 luyện đúng dạng này, kèm cả trạng thái không tới được.
2. Quên trạng thái gốc: deque rỗng ở bước đầu → đọc
front() của deque rỗng, chương trình chết.3. Đề bắt max nhưng vẫn giữ deque tăng: khi tìm max, deque phải giảm dần và điều kiện loại là
dp[back] <= dp[i].Phần 3Convex Hull Trick: mỗi j là một đường thẳng
Bài toán in bài báo. Có $n$ từ, từ thứ $i$ dài $a_i$ ($1 \le a_i \le 100$, $n \le 2 \cdot 10^5$). Ta xếp các từ theo đúng thứ tự thành các dòng, mỗi dòng là một đoạn liên tiếp. Một dòng có tổng độ dài $s$ tốn $s^2 + C$ ($0 \le C \le 10^9$). Tìm tổng chi phí nhỏ nhất.
Với $S$ là tổng tiền tố, dòng cuối gồm các từ $j + 1 \ldots i$:
$dp_i = \min_{j < i} \big( dp_j + (S_i - S_j)^2 \big) + C.$
Không tách biến được, vì có tích $S_i S_j$. Nhưng khai triển ra:
$dp_j + S_i^2 - 2 S_i S_j + S_j^2 = \underbrace{(-2 S_j)}_{m_j} \cdot S_i + \underbrace{(dp_j + S_j^2)}_{b_j} + S_i^2.$
Phần $S_i^2$ không phụ thuộc $j$. Phần còn lại là $m_j \cdot x + b_j$ với $x = S_i$: một đường thẳng theo biến $x$! Bài toán biến thành:
- Thêm đường: tính xong $dp_j$ thì thêm đường $y = m_j x + b_j$ vào tập.
- Truy vấn: cho $x$, tìm $\min_j (m_j x + b_j)$, tức là điểm thấp nhất của các đường tại hoành độ $x$.
Kỹ thuật trả lời hai thao tác này nhanh gọi là Convex Hull Trick (CHT, “mẹo bao lồi”).
Hình học của bao dưới. Vẽ mọi đường lên mặt phẳng, hàm $f(x) = \min_j (m_j x + b_j)$ là một đường gấp khúc lõm gọi là bao dưới. Đi từ trái sang phải, các đoạn của bao dưới có hệ số góc giảm dần: bên trái đường dốc lên nhiều nhất thắng, bên phải đường dốc xuống nhiều nhất thắng. Có những đường không bao giờ chạm bao dưới, gọi là đường thừa: bỏ đi không ảnh hưởng gì.
Hình 2. Năm đường thẳng (tím) và bao dưới (dải xanh nhạt). Đường $d_3$: $y = 1{,}5$ (nét đứt) luôn nằm trên bao dưới nên là đường thừa. Các điểm cam là chỗ bao dưới đổi đường; thứ tự các đường trên bao dưới là $d_1, d_2, d_4, d_5$, đúng thứ tự hệ số góc giảm dần.
Khi nào đường giữa bị thừa? Giả sử đã có ba đường $a, b, c$ với $m_a > m_b > m_c$ ($c$ là đường vừa thêm). Gọi $x_{ab}$ là hoành độ giao điểm của $a$ và $b$: bên phải $x_{ab}$ thì $b$ thấp hơn $a$. Gọi $x_{ac}$ là giao điểm của $a$ và $c$: bên phải $x_{ac}$ thì $c$ thấp hơn $a$. Nếu $x_{ac} \le x_{ab}$ thì ở mọi $x$, hoặc $a$ thấp hơn $b$ (khi $x < x_{ab}$), hoặc $c$ thấp hơn $b$: $b$ thừa. Viết thành phép nhân để tránh chia số thực:
$x_{ac} \le x_{ab} \iff \dfrac{b_c - b_a}{m_a - m_c} \le \dfrac{b_b - b_a}{m_a - m_b} \iff (b_c - b_a)(m_a - m_b) \le (b_b - b_a)(m_a - m_c).$
(Hai mẫu đều dương vì $m_a > m_b > m_c$ nên nhân chéo không đổi chiều.)
CHT với deque khi mọi thứ đơn điệu. Trong bài in bài báo, $S_j$ tăng nên hệ số góc $m_j = -2S_j$ giảm dần theo thứ tự thêm, và truy vấn $x = S_i$ tăng dần. Khi đó:
- Đường mới có hệ số góc nhỏ nhất nên luôn nằm ở cuối bao dưới. Trước khi đẩy vào cuối deque, bỏ đường cuối chừng nào nó thừa (điều kiện trên).
- Truy vấn $x$ tăng nên điểm tối ưu trên bao dưới chỉ đi sang phải. Bỏ đường ở đầu deque chừng nào đường thứ hai cho giá trị $\le$ đường đầu, rồi đọc đường đầu.
Mỗi đường vào và ra deque nhiều nhất một lần, cả bài $O(n)$. Em xem mô phỏng trên đồ thị (có thể tự nhập các đường và các truy vấn):
Giờ đọc code thật của bài in bài báo trong khung chạy tay. Mảng dq chứa chỉ số $j$ của các đường còn trên bao dưới, $h$ là đầu, $t$ là cuối (dùng mảng thay deque cho nhanh):
Xem code C++ / Python: convex hull trick cho bài in bài báo (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long S[200005], dp[200005], M[200005], B[200005];
int dq[200005];
long long f(int j, long long x){ return M[j] * x + B[j]; }
bool bad(int a, int b, int c){ // hệ số góc M[a] > M[b] > M[c]: đường b có thừa không?
return (__int128)(B[c] - B[a]) * (M[a] - M[b]) <= (__int128)(B[b] - B[a]) * (M[a] - M[c]);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long C;
cin >> n >> C;
for(int i = 1; i <= n; i++){ cin >> S[i]; S[i] += S[i - 1]; }
int h = 0, t = 0;
dq[t++] = 0; // đường của j = 0: M = 0, B = 0
for(int i = 1; i <= n; i++){
long long x = S[i]; // truy vấn x tăng dần
while(t - h >= 2 && f(dq[h + 1], x) <= f(dq[h], x)) h++;
dp[i] = f(dq[h], x) + x * x + C;
M[i] = -2 * x; B[i] = dp[i] + x * x; // đường mới, hệ số góc giảm dần
while(t - h >= 2 && bad(dq[t - 2], dq[t - 1], i)) t--;
dq[t++] = i;
}
cout << dp[n];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, C = int(data[0]), int(data[1])
S = [0] * (n + 1)
for i in range(n):
S[i + 1] = S[i] + int(data[2 + i])
M = [0] * (n + 1); B = [0] * (n + 1) # đường của j = 0: M = 0, B = 0
dq = [0] * (n + 1); h, t = 0, 1
dp = 0
for i in range(1, n + 1):
x = S[i] # truy vấn x tăng dần
while t - h >= 2 and M[dq[h + 1]] * x + B[dq[h + 1]] <= M[dq[h]] * x + B[dq[h]]:
h += 1
j = dq[h]
dp = M[j] * x + B[j] + x * x + C
M[i] = -2 * x; B[i] = dp + x * x # đường mới, hệ số góc giảm dần
while t - h >= 2:
a, b = dq[t - 2], dq[t - 1]
if (B[i] - B[a]) * (M[a] - M[b]) <= (B[b] - B[a]) * (M[a] - M[i]):
t -= 1 # đường b thừa
else:
break
dq[t] = i; t += 1
print(dp)
main()long long: $b$ cỡ $10^{16}$, hiệu hệ số góc cỡ $10^{7}$. Trong C++ ép sang __int128 khi so sánh (hoặc so sánh bằng long double nếu chấp nhận sai số). Python không lo chuyện này. Dùng <= ở cả hai chỗ để bỏ luôn những đường trùng giao điểm, tránh deque phình ra vô ích. Nếu có hai đường cùng hệ số góc (đề cho $a_i \ge 0$ chẳng hạn), chỉ giữ đường có $b$ nhỏ hơn, nếu không phép nhân chéo sẽ sai.Phần 4Li Chao tree: khi không có gì đơn điệu
Bài toán con ếch trên đồi. Có $n$ cột đá ($n \le 5 \cdot 10^4$), cột $i$ cao $h_i$ ($0 \le h_i \le 10^6$, không theo thứ tự nào). Ếch ở cột 1, muốn tới cột $n$, mỗi bước nhảy từ $j$ tới một cột $i > j$ bất kỳ, tốn $(h_i - h_j)^2 + C$ ($0 \le C \le 10^9$). Chi phí nhỏ nhất?
Khai triển giống hệt phần 3: $dp_i = h_i^2 + C + \min_{j < i} \big( -2h_j \cdot h_i + dp_j + h_j^2 \big)$. Đường thẳng của $j$ có $m_j = -2h_j$, $b_j = dp_j + h_j^2$. Nhưng lần này $h_j$ lộn xộn: đường mới có thể chen vào giữa bao dưới, và truy vấn có thể nhảy lung tung. Deque bó tay.
Li Chao tree là một cây phân đoạn trên trục hoành. Mỗi nút quản lý một đoạn hoành độ $[l, r]$ và giữ đúng một đường: đường thấp nhất tại điểm giữa $mid$ trong số các đường đã đi qua nút đó.
- Thêm đường mới vào nút: so đường mới với đường đang giữ tại $mid$, đường nào thấp hơn ở $mid$ thì ở lại nút. Đường thua chỉ có thể còn thắng ở một phía của $mid$ (hai đường cắt nhau nhiều nhất một lần): nếu nó thắng ở đầu trái $l$ thì giao điểm ở nửa trái, đi xuống con trái; ngược lại đi xuống con phải. Mỗi lần thêm đi đúng một đường từ gốc xuống lá: $O(\log)$.
- Truy vấn tại $x$: đi từ gốc xuống lá chứa $x$, lấy min các đường gặp trên đường đi. Đúng vì đường tốt nhất tại $x$ chắc chắn được giữ ở một nút nào đó trên đường đi này. Cũng $O(\log)$.
Trục hoành có thể tới $10^6$ hoặc lớn hơn. Ở bài này mọi truy vấn đều là các $h_i$ biết trước, nên ta nén toạ độ: chỉ dựng cây trên mảng xs các giá trị $h$ đã sắp xếp, khác nhau. Cây chỉ còn $4n$ nút.
| Bước | Thao tác | Nút gốc giữ (đoạn x ∈ [1, 9], mid = 5) | Đường bị đẩy xuống |
|---|---|---|---|
| 1 | thêm $y = x$ | $y = x$ (cây rỗng) | – |
| 2 | thêm $y = -x + 8$ | tại 5: $5$ so với $3$ → $y = -x + 8$ ở lại | $y = x$ thắng ở $l = 1$ → xuống con trái [1, 5] |
| 3 | thêm $y = 2$ | tại 5: $2 < 3$ → $y = 2$ ở lại | $y = -x + 8$ thua ở $l = 1$ ($7 > 2$) → xuống con phải [6, 9] |
| 4 | hỏi $x = 1$ | gốc: $2$; con trái giữ $y = x$: $1$ | min = 1 |
Bảng 2. Li Chao tree trên các hoành độ 1 … 9. Mỗi nút giữ đường tốt nhất tại điểm giữa của nó; đường thua đi xuống đúng một nhánh, nơi nó còn có thể thắng.
Xem code C++ / Python: li chao tree cho bài con ếch trên đồi (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Line {
ll m, b;
ll get(ll x) const { return m * x + b; }
};
vector<ll> xs; // các hoành độ sẽ được hỏi, đã sắp xếp, khác nhau
vector<Line> tr; // tr[node]: đường "thắng" tại điểm giữa đoạn của node
void addLine(Line nw){
int node = 1, l = 0, r = xs.size() - 1;
while(true){
int mid = (l + r) / 2;
bool lef = nw.get(xs[l]) < tr[node].get(xs[l]);
bool md = nw.get(xs[mid]) < tr[node].get(xs[mid]);
if(md) swap(tr[node], nw); // node giữ đường tốt hơn tại mid
if(l == r) return;
if(lef != md){ node = 2 * node; r = mid; } // giao điểm ở nửa trái
else { node = 2 * node + 1; l = mid + 1; } // giao điểm ở nửa phải
}
}
ll query(int p){ // p: chỉ số của x trong xs
int node = 1, l = 0, r = xs.size() - 1;
ll res = LLONG_MAX;
while(true){
res = min(res, tr[node].get(xs[p]));
if(l == r) return res;
int mid = (l + r) / 2;
if(p <= mid){ node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; ll C;
cin >> n >> C;
vector<ll> h(n);
for(auto &v : h) cin >> v;
xs = h;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
tr.assign(4 * xs.size(), Line{0, (ll)4e18});
ll dp = 0;
addLine({-2 * h[0], h[0] * h[0]}); // dp[0] = 0
for(int i = 1; i < n; i++){
int p = lower_bound(xs.begin(), xs.end(), h[i]) - xs.begin();
dp = query(p) + h[i] * h[i] + C;
addLine({-2 * h[i], dp + h[i] * h[i]});
}
cout << dp;
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n, C = int(data[0]), int(data[1])
h = [int(v) for v in data[2:2 + n]]
xs = sorted(set(h))
size = len(xs)
TM = [0] * (4 * size) # hệ số góc của đường ở mỗi node
TB = [4 * 10**18] * (4 * size) # hệ số tự do (đường "vô cực" ban đầu)
def add(m, b):
node, l, r = 1, 0, size - 1
while True:
mid = (l + r) // 2
xl, xm = xs[l], xs[mid]
lef = m * xl + b < TM[node] * xl + TB[node]
md = m * xm + b < TM[node] * xm + TB[node]
if md: # node giữ đường tốt hơn tại mid
TM[node], m = m, TM[node]
TB[node], b = b, TB[node]
if l == r:
return
if lef != md:
node, r = 2 * node, mid
else:
node, l = 2 * node + 1, mid + 1
def query(p):
x = xs[p]
node, l, r = 1, 0, size - 1
res = TM[node] * x + TB[node]
while l < r:
mid = (l + r) // 2
if p <= mid:
node, r = 2 * node, mid
else:
node, l = 2 * node + 1, mid + 1
v = TM[node] * x + TB[node]
if v < res:
res = v
return res
dp = 0
add(-2 * h[0], h[0] * h[0]) # dp[0] = 0
for i in range(1, n):
dp = query(bisect_left(xs, h[i])) + h[i] * h[i] + C
add(-2 * h[i], dp + h[i] * h[i])
print(dp)
main()Phần 5Chia để trị tối ưu và nhắc qua tối ưu Knuth
Bài toán. Chia dãy $n$ số nguyên dương ($n \le 10^4$, $a_i \le 1000$) thành đúng $K$ đoạn liên tiếp ($K \le 20$), chi phí mỗi đoạn là (tổng đoạn)$^2$. Tìm tổng chi phí nhỏ nhất.
Thêm một chiều cho số đoạn: $dp[g][i] = \min_{j < i} \big( dp[g-1][j] + \text{cost}(j, i) \big)$. Tính thẳng là $O(K n^2)$. Bài này dùng CHT được, nhưng nếu $\text{cost}$ phức tạp hơn (không khai triển thành đường thẳng) thì sao? Ta dùng một nhận xét khác.
Gọi $opt(i)$ là $j$ nhỏ nhất đạt min khi tính $dp[g][i]$. Với rất nhiều hàm chi phí, $opt$ không giảm: $opt(1) \le opt(2) \le \ldots \le opt(n)$. Trực giác: $i$ lùi sang phải thì điểm cắt cuối cùng cũng không có lý do lùi sang trái. Điều kiện đủ thường dùng là bất đẳng thức tứ giác: với $a \le b \le c \le d$,
$\text{cost}(a, c) + \text{cost}(b, d) \le \text{cost}(a, d) + \text{cost}(b, c).$
Hàm (tổng đoạn)$^2$ với số dương thoả điều kiện này. Khi đi thi, nếu không chắc, em viết bản $O(n^2)$ in ra mảng $opt$ trên vài test ngẫu nhiên để kiểm tra nó có tăng dần không.
Chia để trị. Hàm compute(l, r, optl, optr) tính $dp[g][i]$ cho mọi $i \in [l, r]$, biết rằng opt của chúng nằm trong $[optl, optr]$. Lấy $mid = (l + r)/2$, thử mọi $j \in [optl, \min(mid - 1, optr)]$ để có $dp[g][mid]$ và $opt(mid)$. Vì $opt$ không giảm: các $i < mid$ có opt $\le opt(mid)$, các $i > mid$ có opt $\ge opt(mid)$. Gọi đệ quy hai nửa với khoảng opt đã thu hẹp. Mỗi tầng đệ quy tổng số $j$ được thử là $O(n)$, có $\log n$ tầng: mỗi lớp $O(n \log n)$, cả bài $O(K n \log n)$.
Hình 3. Mỗi hàng là một $i$, mỗi cột là một $j$, ô xanh lá là $opt(i)$, tạo thành một bậc thang đi xuống sang phải. Giải hàng giữa ($i = 4$, opt $= 2$) xong thì hàng trên chỉ cần các cột $\le 2$, hàng dưới chỉ cần các cột $\ge 2$ (ô xanh dương); ô xám không bao giờ phải tính.
Em xem khoảng opt co lại thế nào trên một dãy cụ thể. Mỗi ô của bảng là giá trị $dp[g-1][j] + \text{cost}(j, i)$; để ý số ô phải tính so với cả tam giác:
Xem code C++ / Python: chia để trị tối ưu: chia dãy thành K đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long S[100005], prv[100005], cur[100005];
long long cost(int j, int i){ return (S[i] - S[j]) * (S[i] - S[j]); } // đoạn j+1..i
// tính cur[l..r], biết opt của chúng nằm trong [optl, optr]
void compute(int l, int r, int optl, int optr){
if(l > r) return;
int mid = (l + r) / 2, best = optl;
cur[mid] = LLONG_MAX;
for(int j = optl; j <= min(mid - 1, optr); j++){
long long v = prv[j] + cost(j, mid);
if(v < cur[mid]){ cur[mid] = v; best = j; }
}
compute(l, mid - 1, optl, best); // hàng trên: opt <= best
compute(mid + 1, r, best, optr); // hàng dưới: opt >= best
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, K;
cin >> n >> K;
for(int i = 1; i <= n; i++){ cin >> S[i]; S[i] += S[i - 1]; }
for(int i = 1; i <= n; i++) prv[i] = cost(0, i); // 1 đoạn
for(int g = 2; g <= K; g++){
compute(g, n, g - 1, n - 1); // g đoạn: i >= g, j >= g - 1
for(int i = g; i <= n; i++) prv[i] = cur[i];
}
cout << prv[n];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
S = [0] * (n + 1)
for i in range(n):
S[i + 1] = S[i] + int(data[2 + i])
prv = [(S[i]) ** 2 for i in range(n + 1)] # 1 đoạn
for g in range(2, K + 1):
cur = [0] * (n + 1)
stack = [(g, n, g - 1, n - 1)] # (l, r, optl, optr), khử đệ quy
while stack:
l, r, optl, optr = stack.pop()
if l > r:
continue
mid = (l + r) // 2
best, bv, Sm = optl, None, S[mid]
for j in range(optl, min(mid - 1, optr) + 1):
d = Sm - S[j]
v = prv[j] + d * d
if bv is None or v < bv:
bv, best = v, j
cur[mid] = bv
stack.append((l, mid - 1, optl, best)) # hàng trên: opt <= best
stack.append((mid + 1, r, best, optr)) # hàng dưới: opt >= best
prv = cur
print(prv[n])
main()Tối ưu Knuth cho QHĐ trên đoạn. Bài ghép đá ở bài 27 có công thức $dp[l][r] = \min_{l \le k < r} \big(dp[l][k] + dp[k+1][r]\big) + \text{sum}(l, r)$, tốn $O(n^3)$. Gọi $opt[l][r]$ là $k$ tốt nhất. Knuth chứng minh rằng với những hàm chi phí như tổng đoạn (thoả bất đẳng thức tứ giác và đơn điệu theo bao hàm):
$opt[l][r-1] \le opt[l][r] \le opt[l+1][r].$
Vậy khi tính $dp[l][r]$ chỉ cần thử $k$ trong khoảng đó. Cộng theo từng độ dài đoạn, các khoảng này “nối đuôi” nhau nên tổng chỉ còn $O(n^2)$. Bài tập 8 cài đặt đúng ý này.
| Dạng công thức / dấu hiệu | Kỹ thuật | Độ phức tạp | Ví dụ |
|---|---|---|---|
| $\text{cost}(j, i) = f(i) + g(j)$, $j$ chạy trên tiền tố | min tiền tố (tách biến) | $O(n)$ | phần 1, bài tập 1 |
| $j$ trong cửa sổ $[i - k, i - 1]$ hoặc $[i - R, i - L]$ | deque đơn điệu | $O(n)$ | phần 2, bài tập 2, 3 |
| $\text{cost}$ có tích $x_i \cdot y_j$, hệ số góc và truy vấn đơn điệu | CHT bằng deque | $O(n)$ | phần 3, bài tập 4, 6 |
| có tích $x_i \cdot y_j$, không đơn điệu | Li Chao tree | $O(n \log n)$ | phần 4, bài tập 5 |
| chia thành $K$ đoạn, $opt$ không giảm | chia để trị tối ưu | $O(K n \log n)$ | phần 5, bài tập 7 |
| QHĐ trên đoạn, $opt[l][r-1] \le opt[l][r] \le opt[l+1][r]$ | tối ưu Knuth | $O(n^2)$ | bài tập 8 |
Bảng 3. Bảng tra nhanh các kỹ thuật tối ưu QHĐ trong bài.
- Frog 2 (AtCoder Educational DP Contest B) (Dễ)
- Nhảy Lò Cò (Trung bình)
- Trò Chơi 2 (DPGAME2) (Trung bình)
- Mua Hàng (HSG9 Hà Nội 2025 – Bài 5) (Khá)
- Trò Chơi (DPRCDIE) (Khá)
- Trò Chơi (HSG12 Hà Nội 2025 – Bài 4) (Khó)
Bài tậpLuyện tối ưu quy hoạch động
Con đường gồm $n$ đoạn, đoạn $i$ cao $h_i$ ($n \le 2000$, $0 \le h_i \le 100$). Cần đắp, xẻ để độ cao mới $b_i$ thoả $b_1 \ge b_2 \ge \ldots \ge b_n$ (đường dốc xuống, không có chỗ đi lên) và $0 \le b_i \le 100$. Chi phí là $\sum (h_i - b_i)^2$. Tìm chi phí nhỏ nhất.
5
3 5 2 4 14📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
best. Tổng $O(101 \cdot n)$. Với mẫu, một cách tối ưu là $b = [4, 4, 3, 3, 1]$, chi phí $1 + 1 + 1 + 1 + 0 = 4$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
const int V = 100;
int n;
cin >> n;
vector<long long> dp(V + 1, 0), nd(V + 1);
for(int i = 0; i < n; i++){
long long h;
cin >> h;
long long best = LLONG_MAX; // min hậu tố dp[v..V]
for(int v = V; v >= 0; v--){
best = min(best, dp[v]);
nd[v] = best + (h - v) * (h - v);
}
dp = nd;
}
cout << *min_element(dp.begin(), dp.end());
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
V = 100
dp = [0] * (V + 1)
for i in range(n):
h = int(data[1 + i])
nd = [0] * (V + 1)
best = float('inf') # min hậu tố dp[v..V]
for v in range(V, -1, -1):
if dp[v] < best:
best = dp[v]
nd[v] = best + (h - v) * (h - v)
dp = nd
print(min(dp))
main()Có $n$ chú bò xếp hàng, chú thứ $i$ có năng suất $e_i$ ($n \le 10^5$, $0 \le e_i \le 10^9$). Chọn một số chú đi cắt cỏ sao cho không có quá $k$ chú liên tiếp trong hàng cùng được chọn ($1 \le k \le n$). Tổng năng suất lớn nhất là bao nhiêu?
5 2
1 2 3 4 512📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> e(n + 2, 0), dp(n + 2, 0);
long long total = 0;
for(int i = 1; i <= n; i++){ cin >> e[i]; total += e[i]; }
int w = k + 1; // mọi w chú liên tiếp có 1 chú nghỉ
deque<int> dq;
dq.push_back(0);
for(int i = 1; i <= n + 1; i++){
while(dq.front() < i - w) dq.pop_front();
dp[i] = e[i] + dp[dq.front()]; // chú i nghỉ
while(!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
dq.push_back(i);
}
cout << total - dp[n + 1];
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
e = [0] + [int(x) for x in data[2:2 + n]] + [0]
w = k + 1 # mọi w chú liên tiếp có 1 chú nghỉ
dp = [0] * (n + 2)
dq = deque([0])
for i in range(1, n + 2):
while dq[0] < i - w:
dq.popleft()
dp[i] = e[i] + dp[dq[0]] # chú i nghỉ
while dq and dp[dq[-1]] >= dp[i]:
dq.pop()
dq.append(i)
print(sum(e) - dp[n + 1])
main()Có $n$ hòn đá xếp thẳng hàng giữa hai bờ suối, bờ trái là vị trí $0$, các hòn đá là $1 \ldots n$, bờ phải là $n + 1$. Đặt chân lên hòn đá $i$ được $a_i$ điểm ($|a_i| \le 10^9$, có thể âm). Mỗi bước nhảy dài từ $L$ tới $R$ vị trí ($1 \le L \le R \le n + 1$, $n \le 2 \cdot 10^5$). Đi từ bờ trái sang bờ phải, tổng điểm lớn nhất là bao nhiêu? Nếu không thể sang bờ, in NO.
5 2 3
2 -5 4 -1 34📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, L, R;
cin >> n >> L >> R;
vector<long long> a(n + 2, 0), dp(n + 2, 0);
vector<char> ok(n + 2, 0);
for(int i = 1; i <= n; i++) cin >> a[i];
ok[0] = 1;
deque<int> dq; // dp giảm dần
for(int i = 1; i <= n + 1; i++){
int j = i - L; // j vừa đủ xa để nhảy tới i
if(j >= 0 && ok[j]){
while(!dq.empty() && dp[dq.back()] <= dp[j]) dq.pop_back();
dq.push_back(j);
}
while(!dq.empty() && dq.front() < i - R) dq.pop_front();
if(!dq.empty()){ ok[i] = 1; dp[i] = a[i] + dp[dq.front()]; }
}
if(ok[n + 1]) cout << dp[n + 1];
else cout << "NO";
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, L, R = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]] + [0]
dp = [None] * (n + 2) # None: không tới được
dp[0] = 0
dq = deque() # dp giảm dần
for i in range(1, n + 2):
j = i - L # j vừa đủ xa để nhảy tới i
if j >= 0 and dp[j] is not None:
while dq and dp[dq[-1]] <= dp[j]:
dq.pop()
dq.append(j)
while dq and dq[0] < i - R:
dq.popleft()
if dq:
dp[i] = a[i] + dp[dq[0]]
print('NO' if dp[n + 1] is None else dp[n + 1])
main()Có $n$ kiện hàng xếp theo thứ tự, kiện $i$ nặng $w_i$ ($n \le 2 \cdot 10^5$, $1 \le w_i \le 1000$). Xe chở nhiều chuyến, mỗi chuyến chở một đoạn liên tiếp các kiện. Xe chạy tốt nhất khi chở đúng $T$ ($1 \le T \le 10^6$): một chuyến chở tổng $s$ tốn $(s - T)^2 + P$ ($0 \le P \le 10^9$). Tìm tổng chi phí nhỏ nhất để chở hết.
6 6 4
2 3 4 1 5 215📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
__int128 khi nhân chéo.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[200005], M[200005], B[200005];
int dq[200005];
long long f(int j, long long x){ return M[j] * x + B[j]; }
bool bad(int a, int b, int c){
return (__int128)(B[c] - B[a]) * (M[a] - M[b]) <= (__int128)(B[b] - B[a]) * (M[a] - M[c]);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long T, P;
cin >> n >> T >> P;
for(int i = 1; i <= n; i++){ cin >> S[i]; S[i] += S[i - 1]; }
int h = 0, t = 0;
dq[t++] = 0; // M[0] = B[0] = 0
long long dp = 0;
for(int i = 1; i <= n; i++){
long long x = S[i] - T; // điểm truy vấn, tăng dần
while(t - h >= 2 && f(dq[h + 1], x) <= f(dq[h], x)) h++;
dp = f(dq[h], x) + x * x + P;
M[i] = -2 * S[i]; B[i] = dp + S[i] * S[i];
while(t - h >= 2 && bad(dq[t - 2], dq[t - 1], i)) t--;
dq[t++] = i;
}
cout << dp;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, T, P = int(data[0]), int(data[1]), int(data[2])
S = [0] * (n + 1)
for i in range(n):
S[i + 1] = S[i] + int(data[3 + i])
M = [0] * (n + 1); B = [0] * (n + 1)
dq = [0] * (n + 1); h, t = 0, 1
dp = 0
for i in range(1, n + 1):
x = S[i] - T # điểm truy vấn, tăng dần
while t - h >= 2 and M[dq[h + 1]] * x + B[dq[h + 1]] <= M[dq[h]] * x + B[dq[h]]:
h += 1
j = dq[h]
dp = M[j] * x + B[j] + x * x + P
M[i] = -2 * S[i]; B[i] = dp + S[i] * S[i]
while t - h >= 2:
a, b = dq[t - 2], dq[t - 1]
if (B[i] - B[a]) * (M[a] - M[b]) <= (B[b] - B[a]) * (M[a] - M[i]):
t -= 1
else:
break
dq[t] = i; t += 1
print(dp)
main()Có $n$ trạm xe buýt đánh số $1 \ldots n$ ($n \le 5 \cdot 10^4$). Từ trạm $j$ có thể đi thẳng tới bất kỳ trạm $i > j$ với giá vé $b_j \cdot a_i$, trong đó $b_j$ là hệ số giá của trạm đi và $a_i$ là hệ số của trạm đến ($1 \le a_i, b_i \le 10^6$, không theo thứ tự nào). Tìm chi phí nhỏ nhất để đi từ trạm 1 tới trạm $n$ (có thể đổi xe nhiều lần).
5
3 8 2 6 5
5 9 1 4 215📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Line { ll m, b; ll get(ll x) const { return m * x + b; } };
vector<ll> xs;
vector<Line> tr;
void addLine(Line nw){
int node = 1, l = 0, r = xs.size() - 1;
while(true){
int mid = (l + r) / 2;
bool lef = nw.get(xs[l]) < tr[node].get(xs[l]);
bool md = nw.get(xs[mid]) < tr[node].get(xs[mid]);
if(md) swap(tr[node], nw);
if(l == r) return;
if(lef != md){ node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
ll query(int p){
int node = 1, l = 0, r = xs.size() - 1;
ll res = LLONG_MAX;
while(true){
res = min(res, tr[node].get(xs[p]));
if(l == r) return res;
int mid = (l + r) / 2;
if(p <= mid){ node = 2 * node; r = mid; }
else { node = 2 * node + 1; l = mid + 1; }
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n), b(n);
for(auto &v : a) cin >> v;
for(auto &v : b) cin >> v;
xs = a;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
tr.assign(4 * xs.size(), Line{0, (ll)4e18});
ll dp = 0;
addLine({b[0], 0}); // trạm 1: dp = 0
for(int i = 1; i < n; i++){
int p = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
dp = query(p);
addLine({b[i], dp});
}
cout << dp;
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [int(v) for v in data[1:1 + n]]
b = [int(v) for v in data[1 + n:1 + 2 * n]]
xs = sorted(set(a))
size = len(xs)
TM = [0] * (4 * size)
TB = [4 * 10**18] * (4 * size)
def add(m, c):
node, l, r = 1, 0, size - 1
while True:
mid = (l + r) // 2
xl, xm = xs[l], xs[mid]
lef = m * xl + c < TM[node] * xl + TB[node]
md = m * xm + c < TM[node] * xm + TB[node]
if md:
TM[node], m = m, TM[node]
TB[node], c = c, TB[node]
if l == r:
return
if lef != md:
node, r = 2 * node, mid
else:
node, l = 2 * node + 1, mid + 1
def query(p):
x = xs[p]
node, l, r = 1, 0, size - 1
res = TM[node] * x + TB[node]
while l < r:
mid = (l + r) // 2
if p <= mid:
node, r = 2 * node, mid
else:
node, l = 2 * node + 1, mid + 1
v = TM[node] * x + TB[node]
if v < res:
res = v
return res
dp = 0
add(b[0], 0) # trạm 1: dp = 0
for i in range(1, n):
dp = query(bisect_left(xs, a[i]))
add(b[i], dp)
print(dp)
main()Có $n$ mảnh đất hình chữ nhật, mảnh $i$ có kích thước $w_i \times h_i$ ($n \le 5 \cdot 10^4$, $1 \le w_i, h_i \le 10^6$). Người bán cho mua theo nhóm: một nhóm mảnh đất có giá bằng (chiều rộng lớn nhất trong nhóm) × (chiều dài lớn nhất trong nhóm). Mỗi mảnh thuộc đúng một nhóm. Tìm tổng chi phí nhỏ nhất để mua hết.
4
100 1
15 15
20 5
1 100500📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll W[50005], H[50005], dp[50005], M[50005], B[50005];
int dq[50005];
ll f(int j, ll x){ return M[j] * x + B[j]; }
bool bad(int a, int b, int c){
return (__int128)(B[c] - B[a]) * (M[a] - M[b]) <= (__int128)(B[b] - B[a]) * (M[a] - M[c]);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<pair<ll, ll>> p(n);
for(auto &q : p) cin >> q.first >> q.second;
sort(p.begin(), p.end());
vector<pair<ll, ll>> keep;
ll mh = 0;
for(int i = n - 1; i >= 0; i--) // bỏ mảnh bị "che"
if(p[i].second > mh){ keep.push_back(p[i]); mh = p[i].second; }
reverse(keep.begin(), keep.end()); // w tăng, h giảm
int m = keep.size();
for(int i = 1; i <= m; i++){ W[i] = keep[i - 1].first; H[i] = keep[i - 1].second; }
int h = 0, t = 0;
M[0] = H[1]; B[0] = 0; dq[t++] = 0; // đường của j: M = H[j+1], B = dp[j]
for(int i = 1; i <= m; i++){
while(t - h >= 2 && f(dq[h + 1], W[i]) <= f(dq[h], W[i])) h++;
dp[i] = f(dq[h], W[i]);
if(i == m) break;
M[i] = H[i + 1]; B[i] = dp[i];
while(t - h >= 2 && bad(dq[t - 2], dq[t - 1], i)) t--;
dq[t++] = i;
}
cout << dp[m];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = sorted((int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n))
keep, mh = [], 0
for w, h in reversed(p): # bỏ mảnh bị "che"
if h > mh:
keep.append((w, h)); mh = h
keep.reverse() # w tăng, h giảm
m = len(keep)
W = [0] + [w for w, _ in keep]
H = [0] + [h for _, h in keep]
M = [0] * (m + 1); B = [0] * (m + 1)
M[0] = H[1] # đường của j: M = H[j+1], B = dp[j]
dq = [0] * (m + 1); h, t = 0, 1
dp = 0
for i in range(1, m + 1):
x = W[i]
while t - h >= 2 and M[dq[h + 1]] * x + B[dq[h + 1]] <= M[dq[h]] * x + B[dq[h]]:
h += 1
j = dq[h]
dp = M[j] * x + B[j]
if i == m:
break
M[i] = H[i + 1]; B[i] = dp
while t - h >= 2:
a, b = dq[t - 2], dq[t - 1]
if (B[i] - B[a]) * (M[a] - M[b]) <= (B[b] - B[a]) * (M[a] - M[i]):
t -= 1
else:
break
dq[t] = i; t += 1
print(dp)
main()Phòng thi có $n$ thí sinh ngồi một hàng, thí sinh $i$ có “độ nghịch” $a_i$ ($n \le 3000$, $0 \le a_i \le 10^9$). Cần chia hàng thành đúng $K$ đoạn liên tiếp khác rỗng ($1 \le K \le \min(n, 40)$), mỗi đoạn giao cho một giám thị. Độ vất vả của giám thị coi đoạn $[l, r]$ là $(r - l + 1) \cdot (a_l + \ldots + a_r)$. Tìm tổng độ vất vả nhỏ nhất.
6 3
5 2 8 1 7 352📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cost. Tổng $O(K n \log n)$. Mẫu: $[5, 2]$, $[8, 1]$, $[7, 3]$ cho $14 + 18 + 20 = 52$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[3005], prv[3005], cur[3005];
long long cost(int j, int i){ return (long long)(i - j) * (S[i] - S[j]); }
void compute(int l, int r, int optl, int optr){
if(l > r) return;
int mid = (l + r) / 2, best = optl;
cur[mid] = LLONG_MAX;
for(int j = optl; j <= min(mid - 1, optr); j++){
long long v = prv[j] + cost(j, mid);
if(v < cur[mid]){ cur[mid] = v; best = j; }
}
compute(l, mid - 1, optl, best);
compute(mid + 1, r, best, optr);
}
int main(){
int n, K;
cin >> n >> K;
for(int i = 1; i <= n; i++){ cin >> S[i]; S[i] += S[i - 1]; }
for(int i = 1; i <= n; i++) prv[i] = cost(0, i);
for(int g = 2; g <= K; g++){
compute(g, n, g - 1, n - 1);
for(int i = g; i <= n; i++) prv[i] = cur[i];
}
cout << prv[n];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
S = [0] * (n + 1)
for i in range(n):
S[i + 1] = S[i] + int(data[2 + i])
prv = [i * S[i] for i in range(n + 1)] # 1 đoạn
for g in range(2, K + 1):
cur = [0] * (n + 1)
stack = [(g, n, g - 1, n - 1)]
while stack:
l, r, optl, optr = stack.pop()
if l > r:
continue
mid = (l + r) // 2
best, bv, Sm = optl, None, S[mid]
for j in range(optl, min(mid - 1, optr) + 1):
v = prv[j] + (mid - j) * (Sm - S[j])
if bv is None or v < bv:
bv, best = v, j
cur[mid] = bv
stack.append((l, mid - 1, optl, best))
stack.append((mid + 1, r, best, optr))
prv = cur
print(prv[n])
main()Có $n$ đống đá xếp thành hàng, đống $i$ có $a_i$ viên ($n \le 1500$, $1 \le a_i \le 10^9$). Mỗi lần được ghép hai đống kề nhau thành một, tốn chi phí bằng tổng số viên của đống mới. Ghép tới khi còn một đống. Tìm tổng chi phí nhỏ nhất. (Bản $n \le 300$ đã gặp ở bài 27; lần này $O(n^3)$ là quá chậm.)
5
4 1 3 2 534📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long dp[1505][1505];
int opt[1505][1505];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> S(n + 1, 0);
for(int i = 0; i < n; i++){ long long x; cin >> x; S[i + 1] = S[i] + x; }
for(int i = 0; i < n; i++){ dp[i][i] = 0; opt[i][i] = i; }
for(int len = 2; len <= n; len++)
for(int l = 0; l + len - 1 < n; l++){
int r = l + len - 1;
long long best = LLONG_MAX; int bk = l;
for(int k = opt[l][r - 1]; k <= min(opt[l + 1][r], r - 1); k++){
long long v = dp[l][k] + dp[k + 1][r];
if(v < best){ best = v; bk = k; }
}
dp[l][r] = best + S[r + 1] - S[l];
opt[l][r] = bk;
}
cout << dp[0][n - 1];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
S = [0] * (n + 1)
for i in range(n):
S[i + 1] = S[i] + int(data[1 + i])
dp = [[0] * n for _ in range(n)]
opt = [[i] * n for i in range(n)] # opt[i][i] = i
for ln in range(2, n + 1):
for l in range(n - ln + 1):
r = l + ln - 1
dl, best, bk = dp[l], None, l
hi = min(opt[l + 1][r], r - 1)
for k in range(opt[l][r - 1], hi + 1):
v = dl[k] + dp[k + 1][r]
if best is None or v < best:
best, bk = v, k
dl[r] = best + S[r + 1] - S[l]
opt[l][r] = bk
print(dp[0][n - 1])
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét