Kho lúa (Đề tự luyện HSG Tin quốc gia – Bài 3) – QHĐ chia đoạn, Convex Hull Trick và Aliens trick
Đề bài
Kho lúa
Dọc sông có $N$ làng theo chiều nước chảy, làng $i$ ở vị trí $x_i$ ($x_1 < x_2 < \dots < x_N$) và có $g_i$ tấn lúa. Xây không quá $K$ kho tại các làng, bắt buộc có kho ở làng $N$. Lúa chỉ chở xuôi dòng tới kho gần nhất phía hạ lưu; chở lúa làng $i$ tới kho ở làng $j \ge i$ tốn $g_i (x_j - x_i)$. Tìm tổng chi phí nhỏ nhất.
Giới hạn: $1 \le K \le N \le 2 \cdot 10^5$, $0 \le x_i \le 10^9$, $1 \le g_i \le 1000$.
Subtask:
- Subtask 1 (20%): $N \le 300$.
- Subtask 2 (30%): $K \le 20$.
- Subtask 3 (50%): không có ràng buộc gì thêm.
6 3
1 4 5 9 12 20
2 2 1 5 1 318Kho ở làng 2, 4, 6
(vị trí 4, 9, 20):
2×3 + 1×4 + 1×8 = 18Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Kho lúaLời mở đầu
Ví dụ của đề: kho đặt ở các làng 2, 4, 6. Mũi tên cam là đường chở lúa xuôi dòng, kèm chi phí $g \times$ quãng đường.
Các kho chia dãy làng thành những đoạn liên tiếp, mỗi đoạn $j+1..i$ chở lúa về kho ở làng cuối đoạn $i$. Đặt $G_i = g_1 + \dots + g_i$ và $S_i = g_1 x_1 + \dots + g_i x_i$, chi phí của đoạn đó tính trong $O(1)$:
$$\text{cost}(j+1, i) = \sum_{t=j+1}^{i} g_t (x_i - x_t) = x_i (G_i - G_j) - (S_i - S_j).$$
Thêm kho không bao giờ làm chi phí tăng, nên "không quá $K$ kho" cũng như "đúng $K$ kho" (khi $K \le N$). Bài toán trở thành: chia dãy thành đúng $K$ đoạn, tổng $\text{cost}$ nhỏ nhất – một bài QHĐ chia đoạn kinh điển, độ khó nằm ở chỗ $N, K$ cùng tới $2 \cdot 10^5$.
Cách 1QHĐ chia đoạn – O(N²·K) · 20%
$f[k][i]$ = chi phí nhỏ nhất cho các làng $1..i$ khi dùng $k$ kho và kho cuối ở làng $i$:
$$f[k][i] = \min_{0 \le j < i} \big( f[k-1][j] + \text{cost}(j+1, i) \big), \qquad f[0][0] = 0.$$
Đáp án $= \min_{k \le K} f[k][N]$. Duyệt $j$ lùi và cộng dồn $\text{cost}$ nên mỗi trạng thái tốn $O(N)$. Với $N = 300$ chỉ khoảng $2{,}7 \cdot 10^7$ phép tính.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Cach 1: QHD O(N^2 * K)
// f[k][i] = chi phi nho nhat cho cac lang 1..i khi dung k kho va kho cuoi cung o lang i
int main(){
int n, K;
cin >> n >> K;
vector<ll> x(n + 1), g(n + 1);
for(int i = 1; i <= n; i++) cin >> x[i];
for(int i = 1; i <= n; i++) cin >> g[i];
const ll INF = LLONG_MAX / 4;
vector<vector<ll>> f(K + 1, vector<ll>(n + 1, INF));
f[0][0] = 0;
ll ans = INF;
for(int k = 1; k <= K; k++){
for(int i = 1; i <= n; i++){
ll cost = 0; // chi phi cho lang j+1..i cho ve kho o lang i
for(int j = i - 1; j >= 0; j--){
cost += g[j + 1] * (x[i] - x[j + 1]);
if(f[k - 1][j] < INF) f[k][i] = min(f[k][i], f[k - 1][j] + cost);
}
}
ans = min(ans, f[k][n]); // dung k kho (k <= K)
}
cout << ans;
return 0;
}import sys
# Cach 1: QHD O(N^2 * K)
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
x = [0] + [int(v) for v in data[2:2 + n]]
g = [0] + [int(v) for v in data[2 + n:2 + 2 * n]]
INF = float('inf')
prev = [INF] * (n + 1); prev[0] = 0
ans = INF
for k in range(1, K + 1):
cur = [INF] * (n + 1)
for i in range(1, n + 1):
cost = 0; best = INF
for j in range(i - 1, -1, -1): # nhom lang j+1..i cho ve kho o i
cost += g[j + 1] * (x[i] - x[j + 1])
if prev[j] + cost < best: best = prev[j] + cost
cur[i] = best
ans = min(ans, cur[n]); prev = cur
print(ans)
main()Cách 2QHĐ + Convex Hull Trick – O(N·K) · 50%
Khai triển công thức, phần phụ thuộc $j$ và phần phụ thuộc $i$ tách được:
$$f[k][i] = x_i G_i - S_i + \min_{j} \big( \underbrace{-G_j}_{\text{hệ số góc}} \cdot x_i + \underbrace{f[k-1][j] + S_j}_{\text{tung độ gốc}} \big).$$
Mỗi $j$ là một đường thẳng, cần tìm đường thấp nhất tại hoành độ $X = x_i$. Vì $G_j$ tăng dần nên hệ số góc giảm dần, và $x_i$ cũng tăng dần, nên giữ các đường thẳng trên bao dưới bằng một hàng đợi hai đầu: thêm đường mới ở cuối (bỏ các đường không bao giờ thấp nhất), truy vấn thì bỏ dần ở đầu. Mỗi tầng $k$ tốn $O(N)$.
Bao dưới (đỏ) của các đường thẳng. Khi $X$ tăng, đường tối ưu chuyển dần sang các đường có hệ số góc âm hơn, nên con trỏ đầu hàng đợi chỉ tiến, không lùi.
Với $K \le 20$ thì $O(NK)$ khoảng $4 \cdot 10^6$ phép tính. Lưu ý: khi so sánh để bỏ đường thẳng phải nhân hai số cỡ $10^{17}$ và $10^8$ nên dùng __int128.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 L;
// Cach 2: QHD theo tung so kho + Convex Hull Trick - O(N * K)
// G[i] = g1 + ... + gi, S[i] = g1*x1 + ... + gi*xi
// chi phi lang j+1..i ve kho o i = x[i]*(G[i]-G[j]) - (S[i]-S[j])
int n, K;
vector<ll> x, G, S, prv, cur;
ll val(int j, ll X){ return prv[j] + S[j] - G[j] * X; } // duong thang cua j tai X
bool thua(int a, int b, int c){ // b khong bao gio nho nhat
L ya = prv[a] + S[a], yb = prv[b] + S[b], yc = prv[c] + S[c];
return (yc - ya) * (G[b] - G[a]) <= (yb - ya) * (G[c] - G[a]);
}
int main(){
scanf("%d %d", &n, &K);
x.assign(n + 1, 0); G.assign(n + 1, 0); S.assign(n + 1, 0);
for(int i = 1; i <= n; i++) scanf("%lld", &x[i]);
for(int i = 1; i <= n; i++){ ll g; scanf("%lld", &g); G[i] = G[i - 1] + g; S[i] = S[i - 1] + g * x[i]; }
const ll INF = LLONG_MAX / 4;
prv.assign(n + 1, INF); prv[0] = 0;
ll ans = INF;
vector<int> dq(n + 1);
for(int k = 1; k <= K; k++){
cur.assign(n + 1, INF);
int h = 0, t = 0;
for(int i = 1; i <= n; i++){
int j = i - 1; // them duong thang cua j = i-1
if(prv[j] < INF){
while(t - h >= 2 && thua(dq[t - 2], dq[t - 1], j)) t--;
dq[t++] = j;
}
if(t > h){
while(t - h >= 2 && val(dq[h + 1], x[i]) <= val(dq[h], x[i])) h++; // x[i] tang dan
cur[i] = val(dq[h], x[i]) + x[i] * G[i] - S[i];
}
}
ans = min(ans, cur[n]);
prv = cur;
}
printf("%lld\n", ans);
return 0;
}import sys
# Cach 2: QHD theo tung so kho + Convex Hull Trick - O(N * K)
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
x = [0] + [int(v) for v in data[2:2 + n]]
G = [0] * (n + 1); S = [0] * (n + 1)
for i in range(1, n + 1):
g = int(data[1 + n + i]); G[i] = G[i - 1] + g; S[i] = S[i - 1] + g * x[i]
INF = float('inf')
prv = [INF] * (n + 1); prv[0] = 0; ans = INF
for k in range(1, K + 1):
cur = [INF] * (n + 1); dq = []; h = 0
for i in range(1, n + 1):
j = i - 1
if prv[j] < INF:
yj = prv[j] + S[j]
while len(dq) - h >= 2:
a, b = dq[-2], dq[-1]
ya, yb = prv[a] + S[a], prv[b] + S[b]
if (yj - ya) * (G[b] - G[a]) <= (yb - ya) * (G[j] - G[a]): dq.pop()
else: break
dq.append(j)
if len(dq) > h:
X = x[i]
while len(dq) - h >= 2 and prv[dq[h + 1]] + S[dq[h + 1]] - G[dq[h + 1]] * X <= prv[dq[h]] + S[dq[h]] - G[dq[h]] * X:
h += 1
jj = dq[h]
cur[i] = prv[jj] + S[jj] - G[jj] * X + X * G[i] - S[i]
ans = min(ans, cur[n]); prv = cur
print(ans)
main()Cách 3Aliens trick (phạt mỗi kho λ) + CHT – O(N log C) · 100%
Gọi $OPT(k)$ là chi phí nhỏ nhất khi dùng đúng $k$ kho. Với ví dụ của đề:
Mức giảm khi thêm một kho ngày càng ít (dãy $OPT(k)$ lồi) – điều này đúng cho mọi bộ dữ liệu của bài, vì hàm $\text{cost}$ thoả bất đẳng thức tứ giác.
Cách tìm $\lambda$: tìm kiếm nhị phân. Nếu với $\lambda$ hiện tại lời giải dùng $\ge K$ kho thì phạt còn nhẹ, tăng $\lambda$; ngược lại giảm $\lambda$. Có một chi tiết hay giúp code rất gọn và không phải lo các trường hợp "hoà":
- Với mọi $\lambda$: $dp(\lambda) \le OPT(K) + \lambda K$, tức $h(\lambda) = dp(\lambda) - \lambda K \le OPT(K)$.
- Với $\lambda$ "đúng" thì dấu bằng xảy ra. Hàm $h$ lõm và đỉnh nằm giữa $\lambda$ lớn nhất còn dùng $\ge K$ kho (gọi là $lo$) và $lo + 1$.
Vậy chỉ cần lấy max của $h(\lambda)$ qua các giá trị đã thử (cùng với $lo$ và $lo + 1$) – không cần quan tâm khi có nhiều cách tối ưu thì CHT trả về số kho nào. Cận trên của $\lambda$: chi phí khi chỉ có một kho ở làng $N$ (cộng 1), vì phạt lớn hơn mức đó thì chắc chắn chỉ dùng một kho. Số lần lặp khoảng $\log_2(2 \cdot 10^{17}) \approx 58$, mỗi lần $O(N)$.
Các bạn bấm từng bước ở khung dưới để xem tìm kiếm nhị phân trên $\lambda$ chạy ra sao, và đáp án khớp với $OPT(K)$ tính trâu:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 L;
// Cach 3: "Aliens trick" (phat lam cho moi kho) + Convex Hull Trick - O(N log(chi phi))
int n, K;
vector<ll> x, G, S, dp;
vector<int> cnt, dq;
ll val(int j, ll X){ return dp[j] + S[j] - G[j] * X; }
bool thua(int a, int b, int c){
L ya = dp[a] + S[a], yb = dp[b] + S[b], yc = dp[c] + S[c];
return (yc - ya) * (G[b] - G[a]) <= (yb - ya) * (G[c] - G[a]);
}
// Bai toan khong gioi han so kho, nhung moi kho phai tra them lam
// tra ve (chi phi + lam * so kho) nho nhat va so kho tuong ung
pair<ll,int> giai(ll lam){
dp[0] = 0; cnt[0] = 0;
int h = 0, t = 0; dq[t++] = 0;
for(int i = 1; i <= n; i++){
while(t - h >= 2 && val(dq[h + 1], x[i]) <= val(dq[h], x[i])) h++;
int j = dq[h];
dp[i] = val(j, x[i]) + x[i] * G[i] - S[i] + lam;
cnt[i] = cnt[j] + 1;
while(t - h >= 2 && thua(dq[t - 2], dq[t - 1], i)) t--;
dq[t++] = i;
}
return {dp[n], cnt[n]};
}
int main(){
scanf("%d %d", &n, &K);
x.assign(n + 1, 0); G.assign(n + 1, 0); S.assign(n + 1, 0);
dp.assign(n + 1, 0); cnt.assign(n + 1, 0); dq.assign(n + 1, 0);
for(int i = 1; i <= n; i++) scanf("%lld", &x[i]);
for(int i = 1; i <= n; i++){ ll g; scanf("%lld", &g); G[i] = G[i - 1] + g; S[i] = S[i - 1] + g * x[i]; }
L best = -1;
auto thu = [&](ll lam){ // h(lam) = dp(lam) - lam*K <= dap an, lay max
auto [v, c] = giai(lam);
best = max(best, (L)v - (L)lam * K);
return c;
};
ll lo = 0, hi = x[n] * G[n] - S[n] + 1; // lam = hi: chac chan chi dung 1 kho
while(lo < hi){ // tim lam lon nhat ma so kho >= K
ll mid = lo + (hi - lo + 1) / 2;
if(thu(mid) >= K) lo = mid; else hi = mid - 1;
}
thu(lo); thu(lo + 1);
printf("%lld\n", (ll)best);
return 0;
}import sys
# Cach 3: "Aliens trick" (phat lam cho moi kho) + Convex Hull Trick - O(N log(chi phi))
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
x = [0] + [int(v) for v in data[2:2 + n]]
G = [0] * (n + 1); S = [0] * (n + 1)
for i in range(1, n + 1):
g = int(data[1 + n + i]); G[i] = G[i - 1] + g; S[i] = S[i - 1] + g * x[i]
dp = [0] * (n + 1); cnt = [0] * (n + 1)
def giai(lam):
dq = [0]; h = 0
for i in range(1, n + 1):
X = x[i]
while len(dq) - h >= 2 and dp[dq[h + 1]] + S[dq[h + 1]] - G[dq[h + 1]] * X <= dp[dq[h]] + S[dq[h]] - G[dq[h]] * X:
h += 1
j = dq[h]
dp[i] = dp[j] + S[j] - G[j] * X + X * G[i] - S[i] + lam
cnt[i] = cnt[j] + 1
yi = dp[i] + S[i]
while len(dq) - h >= 2:
a, b = dq[-2], dq[-1]
ya, yb = dp[a] + S[a], dp[b] + S[b]
if (yi - ya) * (G[b] - G[a]) <= (yb - ya) * (G[i] - G[a]): dq.pop()
else: break
dq.append(i)
return dp[n], cnt[n]
best = -1
def thu(lam):
nonlocal best
v, c = giai(lam)
best = max(best, v - lam * K)
return c
lo, hi = 0, x[n] * G[n] - S[n] + 1
while lo < hi:
mid = (lo + hi + 1) // 2
if thu(mid) >= K: lo = mid
else: hi = mid - 1
thu(lo); thu(lo + 1)
print(best)
main()Các bạn bấm chạy tay code C++ để xem từng dòng nhé (mỗi lần gọi giai(lam) khung bên phải hiện bảng $dp, cnt$ và hàng đợi các đường thẳng):
- Tràn số khi so sánh đường thẳng: tung độ gốc tới khoảng $6 \cdot 10^{17}$, hệ số góc tới $2 \cdot 10^8$, tích vượt
long long. Code dùnglong longở chỗ này sai ngay từ subtask 2. - Nhiều lời giải hoà nhau (các làng cách đều, $g_i = 1$): Aliens trick viết theo kiểu "tìm $\lambda$ cho số kho đúng bằng $K$" dễ không bao giờ gặp đúng $K$. Lấy max của $h(\lambda)$ như trên thì không sợ.
- Tham lam (đặt từng kho ở chỗ giảm chi phí nhiều nhất): sai, kể cả với $N$ nhỏ.
- Cách 2 với $K$ lớn: $O(NK)$ khi $N = K = 2 \cdot 10^5$ là $4 \cdot 10^{10}$ – quá thời gian. Cách 1 với subtask 2 còn bị quá bộ nhớ vì mảng $K \times N$.
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Điểm |
|---|---|---|---|---|
| Cách 1 – QHĐ O(N²K) | Đúng | TLE | TLE | 20 |
| Cách 2 – QHĐ + CHT theo từng k | Đúng | Đúng | TLE | 50 |
Cách 3 nhưng so sánh bằng long long | Đúng | Sai | Sai | 20 |
| Cách 3 đầy đủ | Đúng | Đúng | Đúng | 100 |
- 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