Bài 29.1. Kỹ thuật tối ưu DP bằng chia để trị

Bài 29.1: Kỹ thuật tối ưu DP bằng chia để trị

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Chúng ta đã đi qua một chặng đường dài với Lập trình động (Dynamic Programming - DP), từ những bài toán cơ bản đến những kỹ thuật nâng cao. DP là một công cụ cực kỳ mạnh mẽ, cho phép chúng ta giải quyết nhiều vấn đề phức tạp bằng cách chia chúng thành các bài toán con nhỏ hơn và lưu lại kết quả để tránh tính toán lặp.

Tuy nhiên, không phải lúc nào DP cũng nhanh. Có những bài toán mà công thức truy hồi DP của chúng lại yêu cầu duyệt qua một lượng lớn các trạng thái trước đó để tính toán trạng thái hiện tại. Điều này thường dẫn đến độ phức tạp thời gian là O(N^2), thậm chí O(N^3) nếu việc tính toán chi phí mất nhiều thời gian. Khi đối mặt với N có giá trị lớn (ví dụ N = 100,000), O(N^2) là không khả thi.

Lúc này, chúng ta cần đến các kỹ thuật "tối ưu DP". Và hôm nay, chúng ta sẽ cùng nhau tìm hiểu một kỹ thuật tối ưu cực kỳ hiệu quả cho một lớp các bài toán DP nhất định: Kỹ thuật tối ưu DP bằng Chia để trị (Divide and Conquer Optimization)!

Dạng bài toán và thách thức O(N^2)

Kỹ thuật tối ưu bằng chia để trị thường được áp dụng cho các bài toán DP có dạng công thức truy hồi như sau:

dp[i] = min_{0 <= j < i} (dp[j] + cost(j, i))

Ở đây:

dp[i] là giá trị tối ưu (ví dụ: chi phí nhỏ nhất, lợi nhuận lớn nhất) cho bài toán với đầu vào có kích thước i.
cost(j, i) là chi phí hoặc lợi ích liên quan đến việc chuyển từ trạng thái j sang trạng thái i. Thường thì đây là chi phí cho một "đoạn" dữ liệu từ chỉ số j đến i-1 (nếu dùng 0-indexed) hoặc từ j đến i (nếu dùng 1-indexed).

Ví dụ, dp[i] có thể là chi phí nhỏ nhất để xử lý i phần tử đầu tiên của một dãy, và cost(j, i) là chi phí để xử lý k phần tử cuối cùng (a[j...i-1]) trong khi i-j phần tử đầu tiên đã được xử lý với chi phí dp[j].

Để tính dp[i] theo công thức này một cách trực tiếp, ta cần duyệt qua tất cả các giá trị j từ 0 đến i-1. Việc này tốn O(i) thời gian cho mỗi trạng thái dp[i]. Tổng cộng, tính toàn bộ bảng DP từ dp[0] đến dp[N-1] sẽ mất O(N^2) thời gian. Với N lớn, chúng ta cần một phương pháp nhanh hơn.

Điểm mấu chốt: Tính đơn điệu của điểm chia tối ưu

Làm thế nào để tối ưu từ O(N^2)? Kỹ thuật Chia để trị không áp dụng cho mọi bài toán DP dạng trên. Nó chỉ hiệu quả khi bài toán có một thuộc tính đặc biệt liên quan đến điểm mà tại đó giá trị dp[i] đạt cực tiểu.

Gọi opt[i] là một chỉ số j (trong khoảng 0 <= j < i) sao cho dp[i] = dp[j] + cost(j, i) đạt giá trị nhỏ nhất. Nếu có nhiều giá trị j cùng cho ra giá trị nhỏ nhất, opt[i] có thể là chỉ số j nhỏ nhất trong số đó.

Kỹ thuật tối ưu DP bằng Chia để trị áp dụng được khi và chỉ khi thuộc tính sau đúng:

Tính đơn điệu của điểm chia tối ưu: opt[i] <= opt[i+1] cho mọi i (trong miền xác định của opt).

Điều này có nghĩa là khi chúng ta xét các bài toán con lớn dần (từ i sang i+1), điểm chia tối ưu cho bài toán con lớn hơn không bao giờ nằm phía trước điểm chia tối ưu của bài toán con nhỏ hơn. Nó hoặc giữ nguyên, hoặc dịch chuyển về phía sau.

Tính chất đơn điệu này thường được đảm bảo nếu hàm chi phí cost(j, i) thỏa mãn Bất đẳng thức Tứ giác (Quadrangle Inequality): cost(a, c) + cost(b, d) <= cost(a, d) + cost(b, c) cho mọi a <= b <= c <= d.

Tuy nhiên, việc chứng minh trực tiếp tính đơn điệu của opt[i] thường dễ dàng hơn và đủ để áp dụng kỹ thuật này.

Thuật toán Chia để trị để tính DP

Nếu chúng ta biết rằng thuộc tính đơn điệu của opt[i] được thỏa mãn, chúng ta có thể tính toán bảng DP dp[0...N-1] một cách hiệu quả hơn bằng cách sử dụng một hàm đệ quy theo kiểu chia để trị.

Hãy định nghĩa hàm đệ quy Compute(L, R, optL, optR) với ý nghĩa như sau:

Mục đích: Tính các giá trị dp[i] cho tất cả các chỉ số i nằm trong đoạn [L, R] (bao gồm cả L và R).
Giả định: Ta biết rằng chỉ số điểm chia tối ưu opt[i] cho mỗi i trong đoạn [L, R] đều nằm trong đoạn [optL, optR].

Cấu trúc của hàm đệ quy Compute(L, R, optL, optR):

Cơ sở đệ quy (Base Case): Nếu L > R, đoạn [L, R] rỗng, không có gì để tính toán. Dừng đệ quy.
Bước đệ quy (Recursive Step):
- Chọn điểm giữa của đoạn [L, R]: mid = L + (R - L) / 2. Chúng ta sẽ tính dp[mid] tại bước này.
- Để tính dp[mid], ta cần tìm chỉ số j tối ưu. Theo giả định, opt[mid] nằm trong đoạn [optL, optR]. Tuy nhiên, vì j phải nhỏ hơn mid trong công thức dp[mid] = min (dp[j] + cost(j, mid)), nên j chỉ có thể nằm trong đoạn [optL, min(mid - 1, optR)].
- Ta duyệt qua tất cả các giá trị j trong đoạn [optL, min(mid - 1, optR)] để tìm giá trị nhỏ nhất cho dp[j] + cost(j, mid). Cập nhật dp[mid] với giá trị nhỏ nhất tìm được và lưu lại chỉ số j tương ứng làm opt_mid (chỉ số j tối ưu cho dp[mid]).
- Gọi đệ quy cho nửa bên trái: Bây giờ ta cần tính dp[i] cho i trong đoạn [L, mid - 1]. Theo tính chất đơn điệu opt[i] <= opt[mid] cho mọi i < mid, ta biết rằng điểm chia tối ưu opt[i] cho các i trong đoạn [L, mid - 1] phải nằm trong đoạn [optL, opt_mid]. Ta gọi đệ quy: Compute(L, mid - 1, optL, opt_mid).
- Gọi đệ quy cho nửa bên phải: Tương tự, ta cần tính dp[i] cho i trong đoạn [mid + 1, R]. Theo tính chất đơn điệu opt[mid] <= opt[i] cho mọi i > mid, ta biết rằng điểm chia tối ưu opt[i] cho các i trong đoạn [mid + 1, R] phải nằm trong đoạn [opt_mid, optR]. Ta gọi đệ quy: Compute(mid + 1, R, opt_mid, optR).

Độ phức tạp:

Tại mỗi tầng đệ quy, chúng ta chia đoạn [L, R] và đoạn [optL, optR] làm hai. Tổng chiều dài của các đoạn [optL, min(mid-1, optR)] được duyệt qua để tính các giá trị dp[mid] ở một tầng đệ quy là O(N) (tổng của opt_mid - optL ở nửa trái và optR - opt_mid ở nửa phải xấp xỉ optR - optL ban đầu).

Vì có O(log N) tầng đệ quy (do đoạn [L, R] bị chia đôi), tổng số lần tính toán cost(j, i) sẽ là O(N log N), với giả định hàm cost(j, i) có thể tính trong O(1) thời gian. Nếu cost(j, i) mất O(C) thời gian, độ phức tạp tổng thể sẽ là O(N C log N). Để đạt được O(N log N) thực sự, chúng ta thường cần tiền xử lý (ví dụ: mảng cộng dồn) để tính cost trong O(1).

Ví dụ minh họa 1: 1D Clustering (Phân cụm 1 chiều)

Bài toán: Cho N điểm trên một đường thẳng với tọa độ x_0, x_1, ..., x_{N-1} (đã được sắp xếp). Cần phân hoạch N điểm này thành các đoạn con liên tục. Chi phí của một đoạn từ điểm có chỉ số j đến điểm có chỉ số i-1 (tức là các điểm x_j, x_{j+1}, ..., x_{i-1}) là (x_{i-1} - x_j)^2. Tìm cách phân hoạch sao cho tổng chi phí của tất cả các đoạn là nhỏ nhất.

DP: Gọi dp[i] là chi phí nhỏ nhất để phân hoạch i điểm đầu tiên (x_0, ..., x_{i-1}). Điểm cuối cùng x_{i-1} phải nằm trong đoạn cuối cùng. Đoạn cuối cùng này bắt đầu từ điểm x_j nào đó (với 0 <= j < i). Chi phí để phân hoạch i điểm đầu tiên, với đoạn cuối cùng là x_j, ..., x_{i-1} sẽ là dp[j] (chi phí cho j điểm đầu tiên x_0, ..., x_{j-1}) cộng với chi phí của đoạn cuối cùng (x_{i-1} - x_j)^2.

Công thức truy hồi: dp[i] = min_{0 <= j < i} (dp[j] + (x_{i-1} - x_j)^2) Với điều kiện gốc: dp[0] = 0 (chi phí phân hoạch 0 điểm là 0).

Đây chính xác là dạng dp[i] = min_{0 <= j < i} (dp[j] + cost(j, i)) với cost(j, i) = (x_{i-1} - x_j)^2. (Lưu ý sự khác biệt nhỏ về chỉ số trong cost so với dạng tổng quát, điều này phụ thuộc vào cách định nghĩa đoạn).

Hàm cost(j, i) = (x_{i-1} - x_j)^2 thỏa mãn Bất đẳng thức Tứ giác (hoặc có thể chứng minh tính đơn điệu của opt[i]). Do đó, ta có thể áp dụng tối ưu bằng chia để trị.

Cài đặt C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18; // Sử dụng giá trị vô cùng lớn cho long long

vector<long long> x; // Tọa độ các điểm
vector<long long> dp; // Bảng DP: dp[i] = min cost for first i points (x_0..x_{i-1})

// Hàm tính chi phí cho đoạn từ điểm thứ j đến điểm thứ i-1 (0-indexed)
// cost(j, i): segment x_j, ..., x_{i-1}
long long calculate_cost(int j, int i) {
    // Chỉ số i ở đây là kích thước bài toán (1..N), tương ứng với điểm x_{i-1}
    // Chỉ số j ở đây là kích thước bài toán con (0..i-1), tương ứng với điểm x_{j-1}
    // Công thức là dp[i] = min_{0 <= j < i} (dp[j] + cost(j, i))
    // cost(j, i) = cost of segment x_j, ..., x_{i-1}
    // Điểm x_j là điểm thứ j (0-indexed), điểm x_{i-1} là điểm thứ i-1 (0-indexed).
    // Chỉ số trong mảng x là 0 đến N-1.
    // cost(j, i) = (x[i-1] - x[j])^2
    long long diff = x[i - 1] - x[j];
    return diff * diff;
}

// Hàm đệ quy tối ưu DP bằng chia để trị
// Compute(L, R, optL, optR): Tính dp[i] cho i in [L, R], biết opt[i] in [optL, optR]
void Compute(int L, int R, int optL, int optR) {
    if (L > R) {
        return;
    }

    int mid = L + (R - L) / 2; // mid là chỉ số i trong dp[i] (1..N)
    long long min_cost = INF;
    int opt_mid = -1; // Lưu chỉ số j tối ưu cho dp[mid]

    // Tính dp[mid]. opt[mid] nằm trong [optL, min(mid - 1, optR)]
    // j là chỉ số kết thúc của bài toán con trước đó (0..mid-1)
    // Tức là đoạn cuối cùng bắt đầu từ điểm có chỉ số j (0-indexed) trong mảng x.
    // Nếu đoạn cuối là x[j]...x[mid-1], bài toán con trước đó là x[0]...x[j-1], có chi phí dp[j].
    // Vòng lặp cho j: 0 <= j < mid.
    // opt[mid] là j. Theo giả định, opt[mid] thuộc [optL, optR].
    // j phải < mid, nên j thuộc [optL, min(mid - 1, optR)].
    // Cận trên min(mid-1, optR) đảm bảo j luôn < mid và không vượt quá optR.
    // Cận dưới optL đảm bảo j không nhỏ hơn optL.
    // Duyệt j từ optL đến min(mid - 1, optR)
    int j_start = optL;
    int j_end = min(mid - 1, optR); // j phải < mid

    for (int j = j_start; j <= j_end; ++j) {
        long long current_cost = (j == 0 ? 0 : dp[j]) + calculate_cost(j, mid);
        if (current_cost < min_cost) {
            min_cost = current_cost;
            opt_mid = j; // Lưu chỉ số j tối ưu
        }
    }

    dp[mid] = min_cost;

    // Gọi đệ quy cho hai nửa
    // Nửa trái: tính dp[L...mid-1], opt[i] in [optL, opt_mid]
    Compute(L, mid - 1, optL, opt_mid);

    // Nửa phải: tính dp[mid+1...R], opt[i] in [opt_mid, optR]
    Compute(mid + 1, R, opt_mid, optR);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Số lượng điểm
    cin >> N;

    x.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i];
    }

    dp.resize(N + 1, INF);
    dp[0] = 0; // Chi phí phân hoạch 0 điểm là 0

    // Gọi hàm đệ quy: Tính dp[1...N], opt[i] ban đầu nằm trong [0, N-1]
    // opt[i] là chỉ số j (0-indexed)
    Compute(1, N, 0, N - 1);

    cout << dp[N] << endl; // Kết quả là chi phí nhỏ nhất cho N điểm

    return 0;
}

Giải thích Code 1:

Headers và Setup: Bao gồm các thư viện cần thiết, sử dụng long long cho chi phí để tránh tràn số, và định nghĩa INF.
x và dp: x lưu tọa độ các điểm (0-indexed). dp có kích thước N+1, dp[i] lưu chi phí nhỏ nhất để phân hoạch i điểm đầu tiên (x_0 đến x_{i-1}). dp[0] được khởi tạo bằng 0.
calculate_cost(j, i): Hàm này tính chi phí cho đoạn từ điểm có chỉ số j đến i-1 trong mảng x. Theo công thức, chi phí là (x[i-1] - x[j])^2. Chú ý i ở đây tương ứng với kích thước bài toán con (1 đến N), và j tương ứng với điểm bắt đầu của đoạn cuối (0 đến N-1).
Compute(L, R, optL, optR): Đây là hàm đệ quy chính.
- L, R: Phạm vi các chỉ số i trong bảng dp mà chúng ta đang cố gắng tính (dp[L] đến dp[R]).
- optL, optR: Phạm vi có thể có của chỉ số j tối ưu (opt[i]) cho các i trong [L, R].
- Base Case: L > R nghĩa là không có dp nào để tính.
- Recursive Step:
  - Tính mid = L + (R - L) / 2. Ta sẽ tính dp[mid]. mid là kích thước bài toán (1 đến N), tương ứng với điểm x_{mid-1}.
  - Duyệt j từ optL đến min(mid - 1, optR). Tại sao lại là min(mid - 1, optR)?
    - j < mid: Bắt buộc vì đoạn cuối cùng x_j, ..., x_{mid-1} yêu cầu j phải nhỏ hơn mid.
    - j <= optR: Theo giả định đệ quy, opt[mid] nằm trong [optL, optR].
    - Kết hợp lại, j phải nằm trong [optL, min(mid - 1, optR)].
  - Tính current_cost = (j == 0 ? 0 : dp[j]) + calculate_cost(j, mid). Nếu j=0, đoạn cuối cùng bắt đầu từ x_0, bài toán con trước đó có kích thước 0, chi phí là dp[0]. Nếu j > 0, đoạn cuối bắt đầu từ x_j, bài toán con trước đó là x_0...x_{j-1} có kích thước j, chi phí là dp[j].
  - Cập nhật min_cost và opt_mid khi tìm thấy chi phí nhỏ hơn.
  - Sau khi tính xong dp[mid] và tìm được opt_mid, ta chia bài toán con:
    - Nửa trái ([L, mid-1]): Các i ở đây nhỏ hơn mid. Do tính đơn điệu, opt[i] <= opt[mid] = opt_mid. Phạm vi tìm kiếm j cho nửa trái là [optL, opt_mid].
    - Nửa phải ([mid+1, R]): Các i ở đây lớn hơn mid. Do tính đơn điệu, opt[mid] <= opt[i]. Phạm vi tìm kiếm j cho nửa phải là [opt_mid, optR].
main function: Đọc N và tọa độ các điểm, resize dp và khởi tạo dp[0]=0. Gọi Compute(1, N, 0, N-1) để tính dp[1] đến dp[N]. Phạm vi ban đầu cho i là [1, N]. Phạm vi ban đầu cho j (opt[i]) là [0, N-1]. Cuối cùng in ra dp[N].

Ví dụ minh họa 2: Splitting Sequence with Sum Squared Cost

Bài toán: Cho một dãy số nguyên a_0, a_1, ..., a_{N-1}. Cần phân hoạch dãy này thành các đoạn con liên tục. Chi phí của một đoạn con là bình phương tổng các phần tử trong đoạn đó. Tìm cách phân hoạch sao cho tổng chi phí của tất cả các đoạn là nhỏ nhất.

DP: Gọi dp[i] là chi phí nhỏ nhất để phân hoạch i phần tử đầu tiên (a_0, ..., a_{i-1}). Phần tử cuối cùng a_{i-1} phải nằm trong đoạn cuối cùng. Đoạn cuối cùng này bắt đầu từ phần tử a_j nào đó (với 0 <= j < i). Chi phí để phân hoạch i phần tử đầu tiên, với đoạn cuối cùng là a_j, ..., a_{i-1} sẽ là dp[j] (chi phí cho j phần tử đầu tiên a_0, ..., a_{j-1}) cộng với chi phí của đoạn cuối cùng (Sum(a_j, ..., a_{i-1}))^2.

Để tính tổng một đoạn con nhanh chóng, ta sử dụng mảng cộng dồn (prefix sums). Gọi S[i] là tổng của a_0, ..., a_{i-1}. S[0] = 0. S[i] = S[i-1] + a[i-1] cho i > 0. Tổng của đoạn a_j, ..., a_{i-1} là S[i] - S[j].

Công thức truy hồi: dp[i] = min_{0 <= j < i} (dp[j] + (S[i] - S[j])^2) Với điều kiện gốc: dp[0] = 0.

Đây cũng chính xác là dạng dp[i] = min_{0 <= j < i} (dp[j] + cost(j, i)) với cost(j, i) = (S[i] - S[j])^2. Hàm chi phí này cũng thỏa mãn Bất đẳng thức Tứ giác (hoặc có thể chứng minh tính đơn điệu của opt[i]). Do đó, ta có thể áp dụng tối ưu bằng chia để trị.

Cài đặt C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18; // Sử dụng giá trị vô cùng lớn cho long long

vector<long long> a; // Dãy số đầu vào
vector<long long> S; // Mảng prefix sums: S[i] = sum(a[0]...a[i-1])
vector<long long> dp; // Bảng DP: dp[i] = min cost for first i elements (a_0..a_{i-1})

// Hàm tính chi phí cho đoạn từ chỉ số j đến i-1 (0-indexed trong mảng a)
// cost(j, i): segment a_j, ..., a_{i-1}
// i là kích thước bài toán (1..N), j là kích thước bài toán con trước (0..i-1)
long long calculate_cost(int j, int i) {
    // Segment a_j, ..., a_{i-1}
    // Sum = S[i] - S[j]
    long long segment_sum = S[i] - S[j];
    return segment_sum * segment_sum;
}

// Hàm đệ quy tối ưu DP bằng chia để trị
// Compute(L, R, optL, optR): Tính dp[i] cho i in [L, R], biết opt[i] in [optL, optR]
void Compute(int L, int R, int optL, int optR) {
    if (L > R) {
        return;
    }

    int mid = L + (R - L) / 2; // mid là chỉ số i trong dp[i] (1..N)
    long long min_cost = INF;
    int opt_mid = -1; // Lưu chỉ số j tối ưu cho dp[mid]

    // Tính dp[mid]. opt[mid] nằm trong [optL, min(mid - 1, optR)]
    // j là chỉ số kết thúc của bài toán con trước đó (0..mid-1)
    // Nếu đoạn cuối là a[j]...a[mid-1], bài toán con trước đó là a[0]...a[j-1], có chi phí dp[j].
    // Vòng lặp cho j: 0 <= j < mid.
    // opt[mid] là j. Theo giả định, opt[mid] thuộc [optL, optR].
    // j phải < mid, nên j thuộc [optL, min(mid - 1, optR)].
    // Cận trên min(mid-1, optR) đảm bảo j luôn < mid và không vượt quá optR.
    // Cận dưới optL đảm bảo j không nhỏ hơn optL.
    // Duyệt j từ optL đến min(mid - 1, optR)
    int j_start = optL;
    int j_end = min(mid - 1, optR); // j phải < mid

    for (int j = j_start; j <= j_end; ++j) {
        // calculate_cost(j, mid) là cost của segment a[j]...a[mid-1]
        long long current_cost = dp[j] + calculate_cost(j, mid);
        if (current_cost < min_cost) {
            min_cost = current_cost;
            opt_mid = j; // Lưu chỉ số j tối ưu
        }
    }

    dp[mid] = min_cost;

    // Gọi đệ quy cho hai nửa
    // Nửa trái: tính dp[L...mid-1], opt[i] in [optL, opt_mid]
    Compute(L, mid - 1, optL, opt_mid);

    // Nửa phải: tính dp[mid+1...R], opt[i] in [opt_mid, optR]
    Compute(mid + 1, R, opt_mid, optR);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Số lượng phần tử
    cin >> N;

    a.resize(N);
    S.resize(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        S[i + 1] = S[i] + a[i]; // Tính prefix sums
    }

    dp.resize(N + 1, INF);
    dp[0] = 0; // Chi phí phân hoạch 0 phần tử là 0

    // Gọi hàm đệ quy: Tính dp[1...N], opt[i] ban đầu nằm trong [0, N-1]
    // opt[i] là chỉ số j (0-indexed)
    Compute(1, N, 0, N - 1);

    cout << dp[N] << endl; // Kết quả là chi phí nhỏ nhất cho N phần tử

    return 0;
}

Giải thích Code 2:

Headers và Setup: Tương tự ví dụ 1.
a, S, dp: a lưu dãy số đầu vào (0-indexed). S lưu mảng prefix sums (kích thước N+1, S[i] là tổng a[0] đến a[i-1]). dp có kích thước N+1, dp[i] lưu chi phí nhỏ nhất để phân hoạch i phần tử đầu tiên (a_0 đến a_{i-1}). dp[0] được khởi tạo bằng 0.
calculate_cost(j, i): Hàm này tính chi phí cho đoạn từ chỉ số j đến i-1 trong mảng a. Sử dụng prefix sums, tổng đoạn này là S[i] - S[j]. Chi phí là bình phương tổng này.
Compute(L, R, optL, optR): Cấu trúc hàm đệ quy hoàn toàn tương tự ví dụ 1, chỉ khác ở hàm calculate_cost được sử dụng.
- L, R: Phạm vi các chỉ số i trong bảng dp (dp[L] đến dp[R]).
- optL, optR: Phạm vi có thể có của chỉ số j tối ưu (opt[i]) cho các i trong [L, R].
- Base Case: L > R.
- Recursive Step:
  - Tính mid = L + (R - L) / 2. Ta sẽ tính dp[mid]. mid là kích thước bài toán (1 đến N), tương ứng với phần tử cuối a_{mid-1}.
  - Duyệt j từ optL đến min(mid - 1, optR). j là chỉ số kết thúc của bài toán con trước đó (0..mid-1). Nếu đoạn cuối là a[j]...a[mid-1], bài toán con trước đó là a[0]...a[j-1], có chi phí dp[j].
  - Tính current_cost = dp[j] + calculate_cost(j, mid).
  - Cập nhật min_cost và opt_mid.
  - Gọi đệ quy cho hai nửa, sử dụng opt_mid để thu hẹp phạm vi tìm kiếm j cho các bước sau.
main function: Đọc N và dãy số a. Tính mảng prefix sums S. Resize dp và khởi tạo dp[0]=0$. GọiCompute(1, N, 0, N-1)để tínhdp[1]đếndp[N]. Phạm vi ban đầu choilà[1, N]. Phạm vi ban đầu choj(opt[i]) là[0, N-1]. Cuối cùng in radp[N]`.

Bài tập ví dụ:

DSA04013

Có N con Kanguru trong vườn thú, con thứ i có chiều cao bằng A[i]. Con Kanguru có chiều cao X có thể chứa được con có chiều cao bằng Y trong túi của nó nếu như X >= 2*Y. Một con đã chứa một con Kanguru rồi, thì không nhảy vào túi một con Kanguru khác. Các bạn hãy tính toán xem trong trường hợp tối ưu.Số con Kanguru nhìn thấy trong vườn ít nhất là bao nhiêu?

Input Format

Cho số nguyên N số lượng con Kanguru(1 <= N <= 100 000) Dòng tiếp gồm N số nguyên Ai

Constraints

Output Format

In ra đáp án của bài toán.

Ví dụ:

Dữ liệu vào

8
2 5 7 6 9 8 4 2

Dữ liệu ra

Chào bạn, đây là hướng dẫn giải bài DSA04013 "Kanguru" bằng C++ một cách ngắn gọn, tập trung vào ý tưởng chính mà không đưa ra code hoàn chỉnh:

Ý tưởng chính: Để số lượng Kanguru nhìn thấy ít nhất, ta cần nhét được càng nhiều con Kanguru vào túi của các con khác càng tốt. Một con Kanguru có chiều cao X chỉ có thể chứa con có chiều cao Y nếu X >= 2*Y. Để tối ưu, ta nên cố gắng nhét những con nhỏ nhất vào túi của những con vừa đủ lớn.
Sắp xếp: Sắp xếp mảng chiều cao A theo thứ tự tăng dần. Điều này giúp ta dễ dàng tìm kiếm cặp (kanguru nhỏ, kanguru lớn) tiềm năng.
Chiến lược ghép cặp: Sau khi sắp xếp, những con nhỏ nhất nằm ở đầu mảng và những con lớn nhất nằm ở cuối mảng. Ta có thể chia mảng thành hai phần: phần đầu (có thể là con bị nhét) và phần cuối (có thể là con đi nhét). Ta cố gắng ghép con nhỏ nhất còn lại (từ phần đầu) với con lớn nhất đủ điều kiện còn lại (từ phần cuối) hoặc với con nhỏ nhất đủ điều kiện từ phần cuối. Cách hiệu quả nhất là dùng kỹ thuật "hai con trỏ" (two pointers).
Kỹ thuật Hai con trỏ:
- Sử dụng hai con trỏ, một con trỏ left bắt đầu từ đầu mảng (index 0) và một con trỏ right bắt đầu từ giữa mảng (hoặc vị trí thích hợp, ví dụ N/2).
- Con trỏ left đại diện cho con Kanguru nhỏ nhất chưa được nhét.
- Con trỏ right đại diện cho con Kanguru (từ nửa sau mảng) nhỏ nhất chưa được dùng để nhét.
- Lặp và kiểm tra xem con Kanguru tại A[right] có thể nhét con Kanguru tại A[left] hay không (tức là A[right] >= 2 * A[left]).
- Nếu CÓ thể nhét: Ta thành công ghép cặp (A[right], A[left]). Tăng số lượng cặp thành công. Di chuyển cả hai con trỏ lên 1 vị trí (left++, right++) để xét con nhỏ tiếp theo và con lớn tiếp theo.
- Nếu KHÔNG thể nhét: A[right] quá nhỏ để nhét A[left]. Vì A[right] là con nhỏ nhất trong số các ứng viên đi nhét (từ right trở đi) và A[left] là con nhỏ nhất trong số các ứng viên bị nhét (từ left trở đi), nếu A[right] không nhét được A[left], thì A[right] cũng không thể nhét được A[left+1] (vì A[left+1] >= A[left]). Điều này có nghĩa là A[right] không thể dùng làm túi cho A[left] hoặc bất kỳ con nào lớn hơn nó từ phía left. Ta phải tìm một túi khác lớn hơn cho A[left]. Do đó, ta chỉ di chuyển con trỏ right lên 1 vị trí (right++) để xem xét con lớn hơn tiếp theo làm túi cho A[left]. Con A[left] vẫn chờ một túi phù hợp.
- Vòng lặp tiếp tục cho đến khi một trong hai con trỏ ra ngoài phạm vi được xét.
Kết quả: Số Kanguru nhìn thấy ít nhất chính là tổng số Kanguru ban đầu trừ đi số lượng cặp (kanguru bị nhét, kanguru đi nhét) mà ta đã ghép được thành công. Kết quả = N - số_lượng_cặp_thành_công.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.