Bài 29.3. Kỹ thuật Knuth Optimization
Bài 29.3. Kỹ thuật Knuth Optimization
Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Trong thế giới đầy thách thức của Lập trình thi đấu và tối ưu thuật toán, việc giảm thiểu độ phức tạp thời gian là chìa khóa để giải quyết những bài toán lớn. Quy hoạch động (Dynamic Programming - DP) là một công cụ cực kỳ mạnh mẽ, nhưng đôi khi, các công thức truy hồi DP có thể dẫn đến độ phức tạp đa thức bậc cao, phổ biến nhất là O(N^3) hoặc O(N^4). May mắn thay, với một số dạng bài DP đặc biệt, tồn tại những kỹ thuật tối ưu giúp giảm đáng kể thời gian tính toán. Một trong những kỹ thuật mạnh mẽ và thanh lịch đó chính là Kỹ thuật Knuth Optimization, hay còn gọi là Divide and Conquer Optimization (mặc dù tên gọi này đôi khi gây nhầm lẫn với một kỹ thuật khác).
Knuth Optimization giúp chúng ta giảm độ phức tạp của một lớp các bài toán DP từ O(N^3) xuống O(N^2). Nghe thật hấp dẫn phải không? Hãy cùng đi sâu tìm hiểu xem khi nào và làm thế nào để áp dụng "bí kíp" này nhé!
Bài toán DP có cấu trúc đặc biệt
Knuth Optimization áp dụng cho các bài toán Quy hoạch động có công thức truy hồi dạng:
DP[i][j] = min_{i <= k < j} (DP[i][k] + DP[k+1][j] + Cost(i, j))
Ở đây:
DP[i][j]là giá trị tối ưu cho một đoạn hoặc một cấu trúc con liên quan đến các phần tử từ chỉ sốiđếnj.- Chúng ta cần tìm một điểm chia
ktrong đoạn[i, j-1]để tối thiểu hóa tổng của giải pháp cho hai bài toán con[i, k]và[k+1, j]cộng với chi phí kết hợpCost(i, j). - Bài toán con thường được giải quyết theo "độ dài" của đoạn
[i, j], tức là chúng ta tínhDP[i][j]cho các đoạn ngắn trước, rồi dần dần mở rộng độ dài.
Công thức này nếu tính toán một cách ngây thơ sẽ có độ phức tạp O(N^3). Vòng lặp ngoài cùng cho độ dài len (từ 1 đến N). Vòng lặp tiếp theo cho điểm bắt đầu i (từ 0 đến N-len). Điểm kết thúc j sẽ là i + len - 1. Và vòng lặp trong cùng để tìm k sẽ chạy từ i đến j-1, tức là O(len) lần. Tổng cộng là O(N^3).
// Công thức DP O(N^3) cơ bản
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = INF;
for (int k = i; k < j; ++k) { // Vòng lặp tìm k
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, j));
}
}
}
Điều kiện để áp dụng Knuth Optimization
Knuth Optimization không áp dụng được cho mọi bài toán có dạng DP như trên. Nó đòi hỏi hàm chi phí Cost(i, j) và/hoặc bản thân giá trị DP phải thỏa mãn một số điều kiện nhất định. Hai điều kiện chính là:
Điều kiện Tứ giác (Quadrangle Inequality - QI): Đối với chi phí
Cost(i, j), điều kiện này phát biểu rằng:Cost(i, j) + Cost(i', j') <= Cost(i, j') + Cost(i', j)cho mọii <= i' <= j <= j'.Giải thích: Điều kiện này nghe có vẻ hình học, nhưng ý nghĩa của nó trong ngữ cảnh này là: nếu bạn có hai đoạn lồng nhau hoặc giao nhau (
[i, j]và[i', j']vớii <= i' <= j <= j'), thì tổng chi phí của hai đoạn "bên ngoài" ([i, j']và[i', j]) nhỏ hơn hoặc bằng tổng chi phí của hai đoạn "bên trong" ([i, j]và[i', j']). Một cách trực quan, điều này ngụ ý rằng chi phí không tăng quá nhanh khi đoạn được mở rộng.Điều kiện Monotonicity của điểm chia tối ưu: Gọi
K[i][j]là chỉ sốknhỏ nhất mà tại đóDP[i][j]đạt giá trị tối thiểu:K[i][j] = argmin_{i <= k < j} (DP[i][k] + DP[k+1][j] + Cost(i, j))Điều kiện cần có làK[i][j]phải thỏa mãn:K[i][j-1] <= K[i][j] <= K[i+1][j]cho mọii < j.Giải thích: Điều kiện này là trọng tâm của Knuth Optimization. Nó nói rằng điểm chia tối ưu
kcho đoạn[i, j]nằm giữa điểm chia tối ưu cho đoạn[i, j-1](ngắn hơn về bên phải) và điểm chia tối ưu cho đoạn[i+1, j](ngắn hơn về bên trái). Điều này cho phép chúng ta thu hẹp phạm vi tìm kiếm chok. Thay vì duyệtktừiđếnj-1, chúng ta chỉ cần duyệtktừK[i][j-1]đếnK[i+1][j].
Lưu ý quan trọng: Người ta đã chứng minh rằng nếu chi phí Cost(i, j) thỏa mãn điều kiện Tứ giác (QI), VÀ Cost(i, j) cũng thỏa mãn điều kiện Monotonicity (hay gọi là Sum-Monotonicity):
Cost(i, j-1) <= Cost(i, j) và Cost(i+1, j) <= Cost(i, j)
cho mọi i < j.
(Nói cách khác, chi phí tăng hoặc không đổi khi mở rộng đoạn.)
Thì điều kiện Monotonicity của điểm chia tối ưu K[i][j] sẽ tự động được đảm bảo. Vì vậy, trong thực tế, chúng ta thường chỉ cần kiểm tra hai điều kiện của hàm Cost(i, j): Tứ giác và Monotonicity.
Kỹ thuật Knuth Optimization hoạt động như thế nào?
Như đã đề cập, Knuth Optimization khai thác điều kiện K[i][j-1] <= K[i][j] <= K[i+1][j].
Khi tính DP[i][j], chúng ta cần tìm K[i][j]. Thuộc tính monotonicity cho biết rằng K[i][j] sẽ nằm giữa K[i][j-1] (đã được tính ở bước trước đó, khi xử lý đoạn [i, j-1] có độ dài nhỏ hơn) và K[i+1][j] (cũng đã được tính khi xử lý đoạn [i+1, j] có độ dài nhỏ hơn).
Vì vậy, vòng lặp tìm k cho DP[i][j] không cần chạy từ i đến j-1 nữa, mà chỉ cần chạy từ K[i][j-1] đến K[i+1][j].
Cấu trúc vòng lặp DP sau khi tối ưu sẽ trông như thế này:
// Cấu trúc DP tối ưu với Knuth Optimization (ví dụ)
// K[i][j] là điểm chia tối ưu cho đoạn [i, j]
for (int len = 1; len <= n; ++len) { // Duyệt độ dài
for (int i = 0; i <= n - len; ++i) { // Duyệt điểm bắt đầu
int j = i + len - 1;
if (len == 1) { // Trường hợp cơ sở
dp[i][j] = ...; // Khởi tạo
k[i][j] = i; // Hoặc một giá trị phù hợp khác
continue;
}
dp[i][j] = INF;
// Phạm vi tìm kiếm k được thu hẹp
// Chú ý chỉ số: K[i][j-1] và K[i+1][j]
// Cần cẩn thận với các trường hợp biên i=0, j=n-1
int start_k = (i == j-1) ? i : k[i][j-1];
int end_k = (i == j-1) ? i : k[i+1][j]; // Hoặc K[i+1][j] nếu j<n-1
// Vòng lặp tìm k được thu hẹp phạm vi
for (int k_val = start_k; k_val <= end_k; ++k_val) {
// Cần điều chỉnh công thức truy hồi và chỉ số k_val phù hợp
// với định nghĩa DP[i][k] và DP[k+1][j]
// Ví dụ: nếu k_val là điểm chia sao cho phần tử k_val nằm ở bài toán con thứ nhất
// thì công thức có thể là dp[i][k_val] + dp[k_val+1][j] + cost(...)
// hoặc nếu k_val là "gốc" của đoạn con [i, j]
// thì công thức có thể là dp[i][k_val-1] + dp[k_val+1][j] + cost(...)
// Chúng ta sẽ làm rõ điều này trong ví dụ OBST.
}
// Cập nhật dp[i][j] và k[i][j]
}
}
Độ phức tạp của cách tính này là O(N^2). Tại sao?
Vòng lặp ngoài cùng cho độ dài len chạy N lần. Vòng lặp thứ hai cho i chạy N lần. Tuy nhiên, vòng lặp trong cùng cho k không chạy N lần nữa. Thay vào đó, đối với một i cố định, khi j tăng từ i+1 đến N-1, phạm vi tìm kiếm cho k ([K[i][j-1], K[i+1][j]]) "trượt" dần về bên phải theo điều kiện K[i][j] <= K[i+1][j]. Tổng số lần chạy của vòng lặp k trên tất cả các giá trị j cho một i cố định là O(N). Tương tự, đối với một j cố định, khi i giảm từ j-1 về 0, phạm vi tìm kiếm cho k "trượt" dần về bên trái theo điều kiện K[i][j-1] <= K[i][j]. Tổng số lần chạy của vòng lặp k trên tất cả các giá trị i cho một j cố định cũng là O(N). Do đó, tổng số lần thực hiện phép tính bên trong vòng lặp k trên toàn bộ bảng DP là O(N^2).
Ví dụ Minh Họa: Bài toán Cây Tìm Kiếm Nhị Phân Tối Ưu (Optimal Binary Search Tree - OBST)
Bài toán OBST là một ví dụ kinh điển để áp dụng Knuth Optimization.
Bài toán: Cho N khóa đã được sắp xếp k_1 < k_2 < ... < k_N. Với mỗi khóa k_i, chúng ta biết tần suất tìm kiếm thành công p_i. Ngoài ra, chúng ta biết tần suất tìm kiếm không thành công trong khoảng giữa k_i và k_{i+1} là q_i (với q_0 cho khoảng nhỏ hơn k_1 và q_N cho khoảng lớn hơn k_N). Xây dựng một cây tìm kiếm nhị phân sao cho tổng chi phí tìm kiếm trung bình là nhỏ nhất. Chi phí tìm kiếm một nút ở độ sâu d (gốc ở độ sâu 1) là d. Chi phí tìm kiếm không thành công tương ứng với độ sâu của nút lá giả (dummy node) tương ứng.
Công thức DP:
Gọi dp[i][j] là chi phí tối thiểu để xây dựng cây tìm kiếm nhị phân tối ưu cho các khóa từ k_i đến k_j.
Nếu cây con cho các khóa k_i đến k_j có gốc là k_r (với i <= r <= j), thì cây con bên trái chứa các khóa k_i đến k_{r-1} và cây con bên phải chứa các khóa k_{r+1} đến k_j.
Khi k_r là gốc, độ sâu của nó là 1 (trong cây con này). Các khóa và khoảng trống tìm kiếm ở cây con trái và phải sẽ tăng độ sâu thêm 1.
Chi phí của cây con gốc k_r là:
dp[i][r-1] (cây con trái) + dp[r+1][j] (cây con phải) + chi_phi_cua_goc_va_toan_bo_la_trong_doan_[i, j].
Chi phí của gốc k_r là p_r * 1 (tính trong cây con).
Chi phí của các tìm kiếm thành công khác p_s (s thuộc [i, j], s != r) sẽ tăng độ sâu thêm 1.
Chi phí của các tìm kiếm không thành công q_t (t thuộc [i-1, j]) cũng sẽ tăng độ sâu thêm 1.
Tổng chi phí tăng thêm cho toàn bộ đoạn [i, j] khi k_r là gốc (tính từ gốc k_r) là tổng tất cả p_s (với s từ i đến j) và tổng tất cả q_t (với t từ i-1 đến j). Gọi tổng này là W(i, j).
W(i, j) = sum_{s=i}^j p_s + sum_{t=i-1}^j q_t.
Lưu ý: q_{-1} không tồn tại, q_N tồn tại. Thường ta đánh số q từ 0 đến N. q_0 cho khoảng trước k_1, q_i cho khoảng giữa k_i và k_{i+1} (với 1 <= i <= N-1), q_N cho khoảng sau k_N.
Với cách đánh số p_1..p_N và q_0..q_N, W(i, j) cho đoạn khóa k_i..k_j (với 1 <= i <= j <= N) sẽ là sum_{s=i}^j p_s + sum_{t=i-1}^j q_t.
*Để đơn giản hóa code và indexing, chúng ta sẽ dùng 0-based index cho mảng p và q (tức là p[0..N-1], q[0..N]) tương ứng với khóa k_0..k_{N-1}. Khi đó, dp[i][j] là chi phí cho khóa k_i đến k_j (0 <= i <= j < N). Gốc k_r với i <= r <= j. Chi phí thêm vào là W(i, j) = sum_{s=i}^j p_s + sum_{t=i}^j q_t. Chú ý: q_i là khoảng trống tìm kiếm trước k_i, q_{i+1} là khoảng trống sau k_i. Khoảng trống trước k_i đến k_j là q_i, q_{i+1}, ..., q_j, q_{j+1}. Vậy W(i, j) = sum_{s=i}^j p_s + sum_{t=i}^{j+1} q_t. Để dễ tính tổng, thường dùng prefix sums. Gọi P[i] = sum_{s=0}^{i-1} p_s và Q[i] = sum_{s=0}^{i-1} q_s. Thì sum_{s=i}^j p_s = P[j+1] - P[i] và sum_{t=i}^{j+1} q_t = Q[j+2] - Q[i]$. Chi phí thêm là(P[j+1] - P[i]) + (Q[j+2] - Q[i])`. Hmm, cách đánh index hơi phức tạp.
Cách đánh index phổ biến trong OBST để DP:
Sử dụng 1-based index cho khóa k_1, ..., k_N, tần suất p_1, ..., p_N. Tần suất không thành công q_0, q_1, ..., q_N.
dp[i][j] là chi phí tối thiểu cho các khóa từ i đến j (1 <= i <= j <= N).
Cây con cho khóa i..j có gốc là k_r (i <= r <= j). Cây con trái cho khóa i..r-1, cây con phải cho khóa r+1..j.
Trường hợp cơ sở: dp[i][i-1] = q_{i-1} (chi phí cho khoảng trống tìm kiếm giữa k_{i-1} và k_i). dp[j+1][j] = q_j.
Công thức truy hồi: dp[i][j] = min_{i <= r <= j} (dp[i][r-1] + dp[r+1][j]) + W(i, j).
Ở đây, W(i, j) là tổng tần suất của tất cả các khóa và khoảng trống tìm kiếm trong đoạn từ k_i đến k_j.
W(i, j) = sum_{s=i}^j p_s + sum_{t=i-1}^j q_t.
Sử dụng prefix sums: P[x] = sum_{s=1}^x p_s, Q[x] = sum_{t=0}^x q_t.
sum_{s=i}^j p_s = P[j] - P[i-1].
sum_{t=i-1}^j q_t = Q[j] - Q[i-2] (với Q[-1] = 0).
Hoặc đơn giản hơn, tính prefix sums cho cả p và q gộp lại:
S[x] = (sum_{s=1}^x p_s) + (sum_{t=0}^x q_t).
Khi đó W(i, j) = sum_{s=i}^j p_s + sum_{t=i-1}^j q_t.
Cách tính W(i, j) tốt nhất là tính prefix sums riêng cho p và q, hoặc gộp lại.
Gọi SumFreq[x] = sum_{s=1}^x p_s + sum_{t=0}^{x-1} q_t.
Khi đó, tổng tần suất cho đoạn từ khoảng trống q_{i-1} đến khoảng trống q_j (bao gồm cả p_i, ..., p_j) là SumFreq[j+1] - SumFreq[i-1]. Đây chính là W(i, j).
Vậy W(i, j) = \sum_{s=i}^j p_s + \sum_{t=i-1}^j q_t.
Với 1 <= i <= j <= N:
W(i, j) = (p_i + ... + p_j) + (q_{i-1} + ... + q_j).
Sử dụng prefix sum pref[x] = sum_{k=1}^x p_k + sum_{k=0}^{x-1} q_k.
pref[0] = q_0. pref[1] = q_0 + p_1 + q_1. pref[i] = q_0 + p_1 + q_1 + ... + p_i + q_i.
Tổng tần suất cho cây con i..j là sum_{k=i}^j p_k + sum_{k=i-1}^j q_k.
sum_{k=i}^j p_k = pref[j] - pref[i-1] - (q_i + ... + q_j).
sum_{k=i-1}^j q_k = pref[j] - pref[i-1] - (p_i + ... + p_j).
Cách đơn giản nhất để tính W(i, j) là dùng prefix sum của cả p và q:
freq_sum[k] = q_0 + p_1 + q_1 + p_2 + ... + p_k + q_k.
freq_sum[0] = q_0.
freq_sum[k] = freq_sum[k-1] + p_k + q_k for k >= 1.
Tổng tần suất cho đoạn từ khóa i đến khóa j (bao gồm p_i..p_j và các q xung quanh nó, tức là từ khoảng trống q_{i-1} đến khoảng trống q_j) là freq_sum[j] - freq_sum[i-1].
Đặt SumFreq[i][j] = sum_{k=i}^j p_k + sum_{k=i-1}^j q_k (SumFreq[i][j] = freq_sum[j] - freq_sum[i-1]).
Công thức DP: dp[i][j] = min_{i <= r <= j} (dp[i][r-1] + dp[r+1][j]) + SumFreq[i][j].
Base cases: dp[i][i-1] = 0 (chi phí cho cây con rỗng) hoặc chính xác hơn là dp[i][i-1] = q_{i-1} (chi phí chỉ gồm nút lá ảo). Thường người ta định nghĩa lại DP state hoặc chi phí thêm vào để dp[i][i-1] = 0.
Một cách định nghĩa DP state để dp[i][i-1] = 0: dp[i][j] là chi phí tối thiểu cho cây con với các khóa từ i đến j. Khi một nút k_r là gốc, nó có độ sâu 1 trong cây con. Các nút con của nó có độ sâu 2, v.v. Tổng chi phí là tổng (tần suất * độ sâu). Nếu gốc là k_r cho đoạn [i, j], thì chi phí là dp[i][r-1] (cây trái) + dp[r+1][j] (cây phải) + tổng tần suất của tất cả các nút và lá ảo trong đoạn [i, j] (vì tất cả chúng tăng độ sâu thêm 1).
Tổng tần suất cho đoạn [i, j] (bao gồm p_i...p_j và q_{i-1}...q_j) là W(i, j) = sum_{k=i}^j p_k + sum_{k=i-1}^j q_k.
Công thức: dp[i][j] = min_{i <= r <= j} (dp[i][r-1] + dp[r+1][j]) + W(i, j).
Base cases: dp[i][i-1] = 0 for i = 1, ..., N+1. (Đoạn rỗng có chi phí 0).
Range của i, j: 1 <= i <= N+1, 0 <= j <= N. Tuy nhiên, chỉ cần i <= j+1. dp[i][j] cần tính cho i từ 1 đến N+1 và j từ 0 đến N.
dp[i][j] for i > j (đoạn rỗng) = 0.
dp[i][i] (đoạn 1 khóa k_i) = p_i + q_{i-1} + q_i.
Let's use 1-based indexing for keys 1..N, p_1..p_N, q_0..q_N.
dp[i][j] = min cost for keys i through j.
dp[i][i-1] = 0 for 1 <= i <= N+1.
W[i][j] = sum_{k=i}^j p_k + sum_{k=i-1}^j q_k. Precompute W[i][j] efficiently using prefix sums of p and q.
pref_p[x] = sum_{k=1}^x p_k, pref_q[x] = sum_{k=0}^x q_k.
W[i][j] = (pref_p[j] - pref_p[i-1]) + (pref_q[j] - pref_q[i-1]).
The DP recurrence:
dp[i][j] = min_{i <= r <= j} (dp[i][r-1] + dp[r+1][j]) + W[i][j] for 1 <= i <= j <= N.
This is exactly the form DP[i][j] = min_{i <= k < j} (DP[i][k] + DP[k+1][j] + Cost(i, j)). Let k=r-1. Then r = k+1. The range for r is i <= r <= j, so i-1 <= k <= j-1. The recurrence becomes dp[i][j] = min_{i-1 <= k <= j-1} (dp[i][k] + dp[k+1][j]) + W[i][j]. The index k represents the last element of the left subtree (or i-1 for empty left, j-1 for full left).
If k is the index of the root r, then i <= k <= j.
dp[i][j] = min_{i <= k <= j} (dp[i][k-1] + dp[k+1][j] + W[i][j]).
Here the Cost(i, j) term is W[i][j].
Does W[i][j] satisfy the Quadrangle Inequality?
W[i][j] + W[i'][j'] <= W[i][j'] + W[i'][j] for i <= i' <= j <= j'.
W[i][j] is the sum of frequencies in the range. Let Sum(a, b) be the sum of all frequencies (p and q) in the range corresponding to keys a through b.
W[i][j] = Sum(i-1, j) using the q index range.
We need to check if Sum(i-1, j) + Sum(i'-1, j') <= Sum(i-1, j') + Sum(i'-1, j) for i <= i' <= j <= j'.
This is the property of sums over intervals. The sum of frequencies is non-negative. For any a <= b <= c <= d, Sum(a, c) + Sum(b, d) = Sum(a, d) + Sum(b, c). (Sum over [a,c] and [b,d] equals sum over [a,d] and [b,c]). Let a = i-1, b = i'-1, c = j, d = j'. Since i <= i' <= j <= j', we have i-1 <= i'-1 <= j <= j'. So W[i][j] + W[i'][j'] = W[i][j'] + W[i'][j]. The equality holds, which is a stronger condition than inequality and is sufficient.
Thus, Cost(i, j) = W[i][j] satisfies QI. Also W[i][j] is non-decreasing with respect to i (decreasing) and j (increasing), satisfying the Monotonicity condition for Cost.
Therefore, Knuth Optimization can be applied to OBST. We can compute K[i][j], the optimal root index r for keys i to j. The monotonicity condition is K[i][j-1] <= K[i][j] <= K[i+1][j].
Let's implement the optimized OBST using C++. We'll use 1-based indexing for keys 1..N, p_1..p_N, q_0..q_N.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Số lượng khóa
cin >> N;
vector<int> p(N + 1); // Tần suất tìm kiếm thành công p[1]...p[N]
vector<int> q(N + 1); // Tần suất tìm kiếm không thành công q[0]...q[N]
for (int i = 1; i <= N; ++i) cin >> p[i];
for (int i = 0; i <= N; ++i) cin >> q[i];
// Tính prefix sums cho tổng tần suất
// sum_freq[k] = q_0 + p_1 + q_1 + ... + p_k + q_k
vector<long long> sum_freq(N + 1, 0);
sum_freq[0] = q[0];
for (int i = 1; i <= N; ++i) {
sum_freq[i] = sum_freq[i-1] + p[i] + q[i];
}
// Hàm tính W(i, j) = sum_{k=i}^j p[k] + sum_{k=i-1}^j q[k]
// Sử dụng prefix sums: W(i, j) = sum_freq[j] - sum_freq[i-1]
auto calculate_W = [&](int i, int j) {
// i, j là chỉ số khóa 1-based
// sum_freq[k] bao gồm q[0]..q[k] và p[1]..p[k]
// W(i, j) cần p[i..j] và q[i-1..j]
// sum_freq[j] = q_0 + p_1 + ... + p_j + q_j
// sum_freq[i-1] = q_0 + p_1 + ... + p_{i-1} + q_{i-1}
// sum_freq[j] - sum_freq[i-1] = (p_i + ... + p_j) + (q_i + ... + q_j)
// Công thức W(i, j) = sum_{k=i}^j p_k + sum_{k=i-1}^j q_k
// Chúng ta cần tính sum_{k=i}^j p_k + sum_{k=i-1}^j q_k
// sum_freq[j] includes q[0] to q[j] and p[1] to p[j]
// sum_freq[i-1] includes q[0] to q[i-1] and p[1] to p[i-1]
// Difference = (p_i + ... + p_j) + (q_i + ... + q_j)
// The standard W definition is Sum P_i..P_j + Sum Q_{i-1}..Q_j
// A better prefix sum for W(i, j) would be prefix_q[j] - prefix_q[i-2] + prefix_p[j] - prefix_p[i-1]
// Let's recalculate prefix sums correctly for W(i, j) = sum(p_i..p_j) + sum(q_{i-1}..q_j)
vector<long long> p_sum(N + 1, 0);
vector<long long> q_sum(N + 1, 0);
for (int k = 1; k <= N; ++k) p_sum[k] = p_sum[k-1] + p[k];
for (int k = 0; k <= N; ++k) q_sum[k] = q_sum[k-1] + q[k]; // q_sum[-1] implicitly 0
long long sum_p = p_sum[j] - p_sum[i-1];
long long sum_q = q_sum[j] - q_sum[i-2]; // q_sum[-1] = 0, so q_sum[i-2] needs care
// Correct q sum: q_sum[j] includes q[0..j], q_sum[i-2] includes q[0..i-2]
// We need sum(q_{i-1}..q_j) = q_sum[j] - q_sum[i-2] if i-1 >= 0.
// If i=1, we need sum(q_0..q_j) = q_sum[j] - q_sum[-1] = q_sum[j]. q_sum[i-2] = q_sum[-1].
// So q_sum[j] - q_sum[i-2] seems correct if we define q_sum[-1] = 0.
// Let's use 0-based prefix sum for q for simplicity in index.
vector<long long> q_sum_0based(N + 2, 0); // q_sum_0based[k] = sum_{t=0}^{k-1} q_t
for(int k=1; k <= N + 1; ++k) q_sum_0based[k] = q_sum_0based[k-1] + q[k-1];
// W(i, j) = sum_{k=i}^j p_k + sum_{k=i-1}^j q_k
// sum p_k (i..j) = p_sum[j] - p_sum[i-1]
// sum q_k (i-1..j) = q_sum_0based[j+1] - q_sum_0based[i-1]
return (p_sum[j] - p_sum[i-1]) + (q_sum_0based[j+1] - q_sum_0based[i-1]);
};
// Tính prefix sums cho W(i, j) một cách hiệu quả hơn
vector<vector<long long>> W(N + 2, vector<long long>(N + 2, 0));
vector<long long> pref_p(N + 1, 0);
vector<long long> pref_q(N + 2, 0); // q_0 to q_N
for(int i = 1; i <= N; ++i) pref_p[i] = pref_p[i-1] + p[i];
for(int i = 0; i <= N; ++i) pref_q[i+1] = pref_q[i] + q[i]; // pref_q[k] = sum q_0..q_{k-1}
// W[i][j] = sum(p_i..p_j) + sum(q_{i-1}..q_j)
// sum(p_i..p_j) = pref_p[j] - pref_p[i-1]
// sum(q_{i-1}..q_j) = pref_q[j+1] - pref_q[i-1]
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; ++j) {
W[i][j] = (pref_p[j] - pref_p[i-1]) + (pref_q[j+1] - pref_q[i-1]);
}
}
// dp[i][j]: min cost for keys i..j (1-based)
vector<vector<long long>> dp(N + 2, vector<long long>(N + 2, 0));
// k[i][j]: optimal root index r for keys i..j (1-based)
vector<vector<int>> k_opt(N + 2, vector<int>(N + 2, 0));
// Base cases: len = 1 (single key)
for (int i = 1; i <= N; ++i) {
int j = i;
dp[i][j] = W[i][j]; // Chi phí khi chỉ có 1 khóa, gốc là chính nó
k_opt[i][j] = i; // Gốc tối ưu cho đoạn [i, i] là i
}
// Base cases: len = 0 (empty range) dp[i][i-1] = 0 already initialized to 0
// DP with Knuth Optimization
for (int len = 2; len <= N; ++len) { // Độ dài đoạn [i, j]
for (int i = 1; i <= N - len + 1; ++i) { // Điểm bắt đầu i
int j = i + len - 1; // Điểm kết thúc j
dp[i][j] = INF;
// Phạm vi tìm kiếm cho gốc k_val (từ i đến j)
// Monotonicity: K[i][j-1] <= K[i][j] <= K[i+1][j]
// Điểm k_opt[i][j] (gốc r) sẽ nằm trong khoảng [k_opt[i][j-1], k_opt[i+1][j]]
// Cần cẩn thận với các trường hợp biên
// Đối với len = 2, [i, i+1]: K[i][i+1] nằm giữa K[i][i] và K[i+1][i+1]
// K[i][i] = i, K[i+1][i+1] = i+1. Vậy K[i][i+1] nằm giữa i và i+1.
// Root for [i, i+1] can be i or i+1. So root k_val = i or i+1.
// Range for k_val should be [k_opt[i][j-1], k_opt[i+1][j]]
// k_opt[i][j-1] is root for keys i..j-1
// k_opt[i+1][j] is root for keys i+1..j
// lower_bound_k: điểm k_val thấp nhất cần xét.
// Nếu len=2, [i, i+1], j-1=i, i+1=i+1. k_opt[i][i]=i, k_opt[i+1][i+1]=i+1. lower=i, upper=i+1.
// Nếu len>2: k_opt[i][j-1] và k_opt[i+1][j] đã được tính từ len nhỏ hơn.
int lower_bound_k = k_opt[i][j-1];
int upper_bound_k = k_opt[i+1][j];
// Đối với len=2, i=1, j=2: k_opt[1][1]=1, k_opt[2][2]=2. Range [1, 2].
// Đối với len=3, i=1, j=3: k_opt[1][2] đã tính, k_opt[2][3] đã tính. Range [k_opt[1][2], k_opt[2][3]].
// Vòng lặp tìm gốc k_val (từ i đến j)
// range of k_val: [lower_bound_k, upper_bound_k]
// min_k is i, max_k is j
// We can iterate k from max(i, k_opt[i][j-1]) to min(j, k_opt[i+1][j])
// Note: k_opt[i][j-1] is the optimal root for keys i..j-1.
// k_opt[i+1][j] is the optimal root for keys i+1..j.
// Indices for k_opt: i goes from 1 to N, j goes from 0 to N.
// k_opt[i][j-1] is valid for i <= j-1. If i > j-1 (i=j), it's base case len=1.
// k_opt[i+1][j] is valid for i+1 <= j. If i+1 > j (i=j), it's base case len=1.
// If len=2, i=1, j=2. k_opt[1][1]=1, k_opt[2][2]=2. Range for k_val is [1, 2].
// k_val can be 1 or 2. k_opt[1][2-1] = k_opt[1][1] = 1. k_opt[1+1][2] = k_opt[2][2] = 2.
// Range is [1, 2]. Correct.
int k_start = k_opt[i][j-1]; // Optimal root for [i, j-1]
int k_end = k_opt[i+1][j]; // Optimal root for [i+1, j]
for (int k_val = k_start; k_val <= k_end; ++k_val) { // k_val là chỉ số của gốc
long long current_cost = dp[i][k_val-1] + dp[k_val+1][j] + W[i][j];
if (current_cost < dp[i][j]) {
dp[i][j] = current_cost;
k_opt[i][j] = k_val;
}
}
}
}
// Kết quả là dp[1][N]
cout << dp[1][N] << endl;
return 0;
}
Giải thích Code C++
Khai báo và Khởi tạo:
N: Số lượng khóa.p: Vector lưu tần suất tìm kiếm thành công (p[1]...p[N]).q: Vector lưu tần suất tìm kiếm không thành công (q[0]...q[N]).dp[i][j]: Bảng DP, lưu chi phí tối thiểu để xây dựng cây cho các khóa từiđếnj. Kích thước(N+2) x (N+2)để xử lý các trường hợp biên (đoạn rỗng). Khởi tạo0hoặcINF.dp[i][i-1] = 0cho đoạn rỗng.k_opt[i][j]: Bảng lưu chỉ số gốc tối ưurcho đoạn khóa từiđếnj. Kích thước(N+2) x (N+2).pref_p,pref_q: Prefix sums để tính nhanh tổng tần suấtW[i][j].pref_p[i]là tổngp_1đếnp_i.pref_q[i]là tổngq_0đếnq_{i-1}.W[i][j]: Bảng lưu tổng tần suấtsum(p_i..p_j) + sum(q_{i-1}..q_j).
Tính W(i, j):
- Tính prefix sums
pref_pvàpref_q. - Tính
W[i][j]cho tất cả các đoạn[i, j]với1 <= i <= j <= Ndựa trên prefix sums. Công thứcW[i][j] = (pref_p[j] - pref_p[i-1]) + (pref_q[j+1] - pref_q[i-1])tính tổngptừiđếnjvàqtừi-1đếnj.
- Tính prefix sums
DP với Knuth Optimization:
- Vòng lặp ngoài cùng
lentừ 1 đếnN: Duyệt theo độ dài của đoạn con. - Vòng lặp thứ hai
itừ 1 đếnN - len + 1: Duyệt điểm bắt đầu của đoạn con.j = i + len - 1là điểm kết thúc. - Trường hợp cơ sở (
len == 1): Đoạn chỉ có một khóak_i. Chi phí làW[i][i], và gốc tối ưu là chính nó (k_opt[i][i] = i). - Trường hợp
len > 1:- Khởi tạo
dp[i][j]vớiINF. - Xác định phạm vi tìm kiếm cho gốc tối ưu
k_val. Dựa vào Knuth Optimization, gốc tối ưuk_opt[i][j]phải nằm trong khoảng[k_opt[i][j-1], k_opt[i+1][j]].k_opt[i][j-1]là gốc tối ưu cho đoạn khóai..j-1(đã tính ở bướclen-1).k_opt[i+1][j]là gốc tối ưu cho đoạn khóai+1..j(cũng đã tính ở bướclen-1). - Vòng lặp tìm
k_val(là chỉ số của gốc): Chạy từk_opt[i][j-1]đếnk_opt[i+1][j]. - Tính chi phí
current_costnếuk_vallà gốc:dp[i][k_val-1](chi phí cây con trái cho khóai..k_val-1) +dp[k_val+1][j](chi phí cây con phải cho khóak_val+1..j) +W[i][j](tổng tần suất của đoạni..j). - Nếu
current_costnhỏ hơndp[i][j]hiện tại, cập nhậtdp[i][j]và lưuk_vallàm gốc tối ưu cho đoạn[i, j]vàok_opt[i][j].
- Khởi tạo
- Vòng lặp ngoài cùng
Kết quả:
- Chi phí tối thiểu cho toàn bộ cây là
dp[1][N].
- Chi phí tối thiểu cho toàn bộ cây là
Code trên hơi khác so với công thức DP[i][j] = min_{i <= k < j} (DP[i][k] + DP[k+1][j] + Cost(i, j)) ở chỗ điểm chia k trong OBST thường là chỉ số của gốc r, chạy từ i đến j. Công thức dp[i][k-1] + dp[k+1][j] tương ứng với việc chia đoạn [i, j] tại gốc k.
Với công thức dp[i][j] = min_{i <= k <= j} (dp[i][k-1] + dp[k+1][j] + W[i][j]), điểm chia tối ưu k_opt[i][j] thỏa mãn k_opt[i][j-1] <= k_opt[i][j] <= k_opt[i+1][j].
Vòng lặp cho k_val chạy từ k_opt[i][j-1] đến k_opt[i+1][j]. Điều này là chính xác theo Knuth Optimization cho dạng này.
Code sử dụng 1-based indexing cho khóa 1..N. dp[i][j] cho khóa i..j.
dp[i][i-1]là đoạn rỗng, có chi phí 0.k_opt[i][i-1]có thể không cần thiết hoặc set giá trị đặc biệt.dp[i][i]là 1 khóa. Chi phí làW[i][i]. Gốck_opt[i][i] = i.dp[i][j]vớilen=j-i+1. Vòng lặplentừ 2.- Đối với
len = 2, đoạn[i, i+1].j = i+1. Ta cần tínhdp[i][i+1].k_opt[i][j-1] = k_opt[i][i] = i.k_opt[i+1][j] = k_opt[i+1][i+1] = i+1. Vòng lặp chok_valchạy từiđếni+1.- Nếu
k_val = i: chi phí =dp[i][i-1] + dp[i+1][i+1] + W[i][i+1] = 0 + W[i+1][i+1] + W[i][i+1]. Hmm, công thức truy hồi làdp[i][k_val-1] + dp[k_val+1][j] + W[i][j]. Nếuk_val = i, cost =dp[i][i-1] + dp[i+1][i+1] + W[i][i+1].dp[i][i-1]=0.dp[i+1][i+1] = W[i+1][i+1]. Cost =W[i+1][i+1] + W[i][i+1]. Wait, OBST cost is sum of depth*freq. If root is i, left is empty (cost 0), right is i+1..j (cost dp[i+1][j]). All freqs i..j increment depth by 1. So cost = dp[i+1][j] + W[i][j]. If root is j, left is i..j-1 (cost dp[i][j-1]), right empty (cost 0). All freqs i..j increment. Cost = dp[i][j-1] + W[i][j]. If root is k, cost = dp[i][k-1] + dp[k+1][j] + W[i][j]. This is correct. Let's re-checkdp[i][i-1] = 0. Yes, empty subtree has cost 0.dp[i+1][i+1]should be cost for key i+1. If root isi, cost for[i, i+1]isdp[i][i-1] + dp[i+1][i+1] + W[i][i+1] = 0 + W[i+1][i+1] + W[i][i+1]. This doesn't seem right.
- Nếu
Let's redefine the DP states and recurrence slightly for clarity with OBST.
dp[i][j] = min cost for keys k_i, ..., k_j AND dummy nodes q_{i-1}, ..., q_j.
Base case: dp[i][i-1] = q_{i-1}. This is the cost if the segment is just the dummy node q_{i-1}.
If we use this, the recurrence should be:
dp[i][j] = min_{i <= r <= j} (dp[i][r-1] + dp[r+1][j]) + sum(p_i..p_j) for i <= j.
Base cases: dp[i][i-1] = 0 for 1 <= i <= N+1. (Cost of empty tree is 0).
Sum of frequencies to add = sum_{k=i}^j p_k + sum_{k=i-1}^j q_k. Let's call this FreqSum(i, j).
dp[i][j] = min_{i <= r <= j} (dp[i][r-1] + dp[r+1][j]) + FreqSum(i, j) for 1 <= i <= j <= N.
Let's adjust the C++ code based on this standard recurrence where dp[i][i-1]=0.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18; // Use long long for INF to avoid overflow
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Số lượng khóa 1..N
cin >> N;
vector<long long> p(N + 1); // Tần suất p[1]...p[N]
vector<long long> q(N + 1); // Tần suất q[0]...q[N]
for (int i = 1; i <= N; ++i) cin >> p[i];
for (int i = 0; i <= N; ++i) cin >> q[i];
// Tính prefix sums cho p và q
vector<long long> pref_p(N + 1, 0);
for (int i = 1; i <= N; ++i) pref_p[i] = pref_p[i-1] + p[i];
vector<long long> pref_q(N + 2, 0); // pref_q[k] = sum_{i=0}^{k-1} q[i]
for (int i = 0; i <= N; ++i) pref_q[i+1] = pref_q[i] + q[i];
// Hàm tính FreqSum(i, j) = sum(p_i..p_j) + sum(q_{i-1}..q_j)
auto calculate_FreqSum = [&](int i, int j) {
// sum(p_i..p_j) = pref_p[j] - pref_p[i-1]
// sum(q_{i-1}..q_j) = pref_q[j+1] - pref_q[i-1]
return (pref_p[j] - pref_p[i-1]) + (pref_q[j+1] - pref_q[i-1]);
};
// dp[i][j]: min cost for keys i..j (1-based)
vector<vector<long long>> dp(N + 2, vector<long long>(N + 2, 0));
// k_opt[i][j]: optimal root index r for keys i..j (1-based)
vector<vector<int>> k_opt(N + 2, vector<int>(N + 2, 0));
// Initialize base cases: len = 0 (empty ranges)
// dp[i][i-1] = 0 is already handled by vector initialization
// Initialize base cases: len = 1 (single key)
for (int i = 1; i <= N; ++i) {
int j = i;
// Cost for key i is p[i]. Dummy nodes q[i-1] and q[i] are also present.
// FreqSum(i, i) = p[i] + q[i-1] + q[i].
dp[i][i] = calculate_FreqSum(i, i);
k_opt[i][i] = i; // Optimal root for [i, i] is i
}
// DP with Knuth Optimization
for (int len = 2; len <= N; ++len) { // Độ dài đoạn [i, j]
for (int i = 1; i <= N - len + 1; ++i) { // Điểm bắt đầu i
int j = i + len - 1; // Điểm kết thúc j
long long current_freq_sum = calculate_FreqSum(i, j);
dp[i][j] = INF;
// Phạm vi tìm kiếm cho gốc k_val (từ i đến j)
// Theo Knuth Optimization: K[i][j-1] <= K[i][j] <= K[i+1][j]
// k_opt[i][j-1] is optimal root for keys i..j-1 (computed at len-1)
// k_opt[i+1][j] is optimal root for keys i+1..j (computed at len-1)
// Root index k_val must be in range [i, j]
// lower bound for k_val is max(i, k_opt[i][j-1])
// upper bound for k_val is min(j, k_opt[i+1][j])
// For OBST, k_opt is root index, i <= k_opt <= j.
// The indices in the Knuth property K[i][j-1] <= K[i][j] <= K[i+1][j]
// refer to the optimal split point k, which is the ROOT INDEX in OBST.
// So K[i][j] is the optimal root for keys i..j.
// k_opt[i][j] will be in range [k_opt[i][j-1], k_opt[i+1][j]].
// We iterate k_val from k_opt[i][j-1] to k_opt[i+1][j].
// Edge cases for k_opt:
// k_opt[i][i-1] is for empty range keys i..i-1. What is its "optimal root"?
// It doesn't have a root. But the property K[i][j-1] <= K[i][j] suggests
// we need k_opt[i][i] for len=2 calculation (i.e., k_opt[i][j-1] when j=i+1 -> j-1=i).
// And k_opt[i+1][i] for len=2 calculation (i.e., k_opt[i+1][j] when j=i+1 -> i+1=j).
// Let's check the optimal root range carefully.
// For dp[i][j], root k can be from i to j.
// Optimal root for keys i..j-1 is k_opt[i][j-1].
// Optimal root for keys i+1..j is k_opt[i+1][j].
// Property: k_opt[i][j-1] <= k_opt[i][j] <= k_opt[i+1][j].
// For dp[i][i+1] (len=2): k_opt[i][i] <= k_opt[i][i+1] <= k_opt[i+1][i+1].
// k_opt[i][i] = i. k_opt[i+1][i+1] = i+1.
// So k_opt[i][i+1] must be i or i+1. The loop runs from i to i+1. Correct.
// For dp[i][j] (len>2): loop runs from k_opt[i][j-1] to k_opt[i+1][j].
// These bounds are valid root indices for the subproblems.
int k_start = k_opt[i][j-1];
int k_end = k_opt[i+1][j];
for (int k_val = k_start; k_val <= k_end; ++k_val) { // k_val là chỉ số của gốc (từ i đến j)
// Cost = cost(left subtree) + cost(right subtree) + cost of this level
// Cost of this level is FreqSum(i, j)
long long current_cost = dp[i][k_val-1] + dp[k_val+1][j] + current_freq_sum;
if (current_cost < dp[i][j]) {
dp[i][j] = current_cost;
k_opt[i][j] = k_val;
}
}
}
}
// Kết quả là dp[1][N]
cout << dp[1][N] << endl;
return 0;
}
Giải thích Code (Phiên bản chỉnh sửa):
- Prefix Sums: Tính
pref_pvàpref_qđể nhanh chóng tính tổng tần suất cho bất kỳ đoạn nào.pref_p[i]là tổngp_1..p_i.pref_q[i]là tổngq_0..q_{i-1}. - FreqSum(i, j): Hàm tiện ích tính tổng tần suất cho các khóa
i..jvà các dummy nodeq_{i-1}..q_j. Công thức(pref_p[j] - pref_p[i-1]) + (pref_q[j+1] - pref_q[i-1])là chính xác dựa trên định nghĩa prefix sums. - Bảng DP và k_opt:
dp[i][j]lưu chi phí min cho khóai..j.k_opt[i][j]lưu chỉ số gốc tối ưurcho khóai..j. - Khởi tạo:
dp[i][i-1] = 0: Chi phí cây con rỗng là 0. Được xử lý bằng cách khởi tạodpbằng 0.len = 1: Đoạn chỉ 1 khóak_i. Chi phí làFreqSum(i, i). Gốc tối ưu lài.
- Vòng lặp DP: Duyệt
lentừ 2 đếnN, sau đó duyệt điểm bắt đầui.jlà điểm kết thúc. - Knuth Optimization: Vòng lặp tìm gốc
k_val(từiđếnj) được giới hạn bởik_opt[i][j-1]vàk_opt[i+1][j].k_opt[i][j-1]là gốc tối ưu cho đoạni..j-1, đã được tính ở bướclen-1.k_opt[i+1][j]là gốc tối ưu cho đoạni+1..j, cũng đã được tính ở bướclen-1.- Phạm vi tìm kiếm cho gốc
k_valcủa đoạni..jlà từk_opt[i][j-1]đếnk_opt[i+1][j]. Vòng lặpfor (int k_val = k_opt[i][j-1]; k_val <= k_opt[i+1][j]; ++k_val)thực hiện việc này.
- Tính Chi phí:
dp[i][k_val-1]là chi phí cây con trái (khóaiđếnk_val-1).dp[k_val+1][j]là chi phí cây con phải (khóak_val+1đếnj).current_freq_sumlà tổng tần suất của tất cả các nút và lá ảo trong đoạni..j, đây là chi phí cộng thêm do tất cả chúng được tăng độ sâu thêm 1 khik_vallà gốc. - Cập nhật: So sánh
current_costvớidp[i][j]và cập nhật nếu tìm thấy chi phí nhỏ hơn, đồng thời lưu lạik_vallàm gốc tối ưu.
Code này chính xác áp dụng Knuth Optimization cho bài toán OBST, giảm độ phức tạp từ O(N^3) xuống O(N^2).
Khi nào nên nghĩ đến Knuth Optimization?
- Bạn gặp một bài toán DP có công thức dạng
DP[i][j] = min_{i <= k < j} (DP[i][k] + DP[k+1][j] + Cost(i, j)). Cost(i, j)chỉ phụ thuộc vàoivàj(không phụ thuộc vàok).- Bạn có thể chứng minh hoặc nghi ngờ rằng hàm
Cost(i, j)thỏa mãn điều kiện Tứ giác (Cost(i, j) + Cost(i', j') <= Cost(i, j') + Cost(i', j)choi <= i' <= j <= j') và Monotonicity (Cost(i, j-1) <= Cost(i, j)vàCost(i+1, j) <= Cost(i, j)choi < j). - Khi đó, rất có thể điều kiện Monotonicity của điểm chia tối ưu
K[i][j](K[i][j-1] <= K[i][j] <= K[i+1][j]) được thỏa mãn, và bạn có thể áp dụng Knuth Optimization.
Bài tập ví dụ:
Gấp đôi dãy số
Một dãy số tự nhiên bắt đầu bởi con số 1 và được thực hiện N-1 phép biến đổi "gấp đôi" dãy số như sau: Với dãy số A hiện tại, dãy số mới có dạng A, x, A trong đó x là số tự nhiên bé nhất chưa xuất hiện trong A. Ví dụ với 2 bước biến đổi, ta có [1] - [1 2 1] - [1 2 1 3 1 2 1]. Các bạn hãy xác định số thứ K trong dãy số cuối cùng là bao nhiêu?
Input Format
Dòng duy nhất chứa 2 số nguyên dương N và K.(1<=N<=50; 1<=K<=2^N - 1)
Constraints
.
Output Format
In ra đáp án của bài toán.
Ví dụ:
Dữ liệu vào
4 2Dữ liệu ra
2Hướng dẫn giải bài "Gấp đôi dãy số" bằng C++ một cách ngắn gọn:
- Quan sát cấu trúc dãy số: Dãy số ở bước N được tạo thành từ dãy số ở bước N-1, số N ở giữa, và lặp lại dãy số ở bước N-1. (ví dụ: A_N = A_{N-1}, N, A_{N-1}).
- Xác định độ dài: Độ dài dãy số ở bước N là
2^N - 1. - Xác định phần tử trung tâm: Phần tử trung tâm của dãy số ở bước N là số N. Vị trí (1-indexed) của nó là
2^(N-1). - Hướng tiếp cận đệ quy: Bài toán có thể giải quyết bằng đệ quy dựa vào cấu trúc này.
- Hàm đệ quy cần hai tham số:
n(tương ứng với số bước biến đổi hiện tại, bắt đầu từ N và giảm dần) vàk(vị trí cần tìm trong dãy số tương ứng vớinbước). - Tính vị trí trung tâm
midcủa dãy số ở bướcn(tức là dãy saun-1phép biến đổi):mid = 2^(n-1). Sử dụng phép dịch bit1LL << (n - 1)để tính2^(n-1)hiệu quả và đảm bảo kiểu dữ liệu đủ lớn (vì K có thể lớn). - Trường hợp 1: Nếu
kbằngmid, thì phần tử cần tìm chính là phần tử trung tâm của dãy số ở bướcn, có giá trị làn. Trả vền. - Trường hợp 2: Nếu
knhỏ hơnmid, phần tử cần tìm nằm ở nửa bên trái của dãy. Nửa bên trái này chính là dãy số ở bướcn-1. Ta tiếp tục tìm phần tử thứktrong dãy số ở bướcn-1. Gọi đệ quy vớin-1vàk. - Trường hợp 3: Nếu
klớn hơnmid, phần tử cần tìm nằm ở nửa bên phải của dãy. Nửa bên phải này cũng là dãy số ở bướcn-1. Vị trí của phần tử trong dãy bên phải làk - mid. Ta tiếp tục tìm phần tử thứk - midtrong dãy số ở bướcn-1. Gọi đệ quy vớin-1vàk - mid.
- Hàm đệ quy cần hai tham số:
- Kiểu dữ liệu: Do K có thể lên tới
2^50 - 1, cần sử dụng kiểu dữ liệulong longcho K và các biến liên quan đến vị trí (nhưmid). N có giới hạn nhỏ (<= 50) nên có thể dùngint. - Hàm chính: Đọc N và K, gọi hàm đệ quy với tham số ban đầu là N và K, in kết quả trả về.
Làm thêm nhiều bài tập miễn phí tại đây
Khóa học liên quan
Giảm giá!
Comments