07.2.Deivide and Conquer Optimization

Giả định chúng ta đã chia được j -1 phần tử đầu tiên ra thành i - 1 mảng con. Khi chúng ta lắp thêm phần tử thứ j vào dãy, chúng ta có i dãy con. Chí phí nhỏ nhất để chia j phần tử thành i dãy có thể bằng giá trị trước đó (đã chia được cho j-1 phần tử) cộng với bình phương của A[i][j], nhưng cũng có thể bằng giá trị của các chia j -2 phần tử trước đó cộng với (A[i][j-1]+A[i][j])2 hoặc cũng có thể lui về hơn nữa.

Như vậy giá trị chi phí nhỏ nhất đó sẽ tùy vào vị trí chúng ta chia lại dãy khi thêm một phần tử vào, gọi vị trí chia đó là k thì k chạy từ i đến j -1.

Từ nhận xét trên, nếu chúng ta gọi dp[i][j] là giá trị nhỏ nhất để chia j phần tử đầu tiên thành i dãy con thì:

dp[i][j] = mini≤k≤j (dp[i-1][k-1] + cost[k][i])

Trong đó: cost[k][i] là tổng bình phương các phần tử từ k đến j của dãy thứ i.

Chúng ta có thể hình dung giá trị của dp[i][j] được điền như sau:

Cài đặt

Để có thể tính cost(i,j) trong O(1) chúng ta tính trước mảng prefix sum --> pref[]

--> cost (i, j) = (pref[j] -pref[i -1])2

Sử dụng vòng lặp bên ngoài duyệt số dãy cần chia (hàng trong bảng trên),

vòng lặp trong duyệt qua từng cột,

vòng lặp trong cùng duyệt qua từng cách kết hợp để điền giá trị vào ô dp[i, j].

Các em có thể tham khảo đoạn code sau:

// Prefix sum array

pref[0] = 0;

for (int i = 0; i < N; i++)

pref[i + 1] = pref[i] + arr[i];

// Initialize the dp array

for (int i = 0; i < N; i++)

dp[0][i] = pref[i + 1] * pref[i + 1];

// Fill in the dp array

for (int i = 1; i < M; i++) {

for (int j = i; j < N; j++) {

dp[i][j] = INT_MAX;

for (int k = 1; k <= j; k++) {

int cost

= (pref[j + 1] - pref[k])

* (pref[j + 1] - pref[k]);

// dp transition

dp[i][j] = min(dp[i][j],

dp[i - 1][k - 1]

+ cost);

}

return dp[M - 1][N - 1];

Nguồn: GeeksforGeeks

Độ phức tạp: O(M * N2)

Optimize bằng Divide and Conquer

Phương pháp này thường được sử dụng để giảm bớt số lần tính toán cho vòng lặp thứ ba trong lúc điền giá trị cho bảng dp[i][j] được xác định bằng công thức chuyển trạng thái tương tự như bài trên.

dp[i][j] = mini≤k≤j (dp[i-1][k-1] + cost[k][i])

Đặt opt(i, j) là chỉ số k sao cho dp[i][j] đạt giá trị tối ưu (min/max) trong bước trước, opt(i, j) được tính theo công thức:

opt[i][j] = argmink<j(dp[i-1][k] + cost[k][j])

Nếu chúng ta có thể chứng minh được opt(i, j) đơn điệu theo hàng, nghĩa là: opt[i][j] ≤ opt[i][j+1] , chúng ta có thể áp dụng kỹ thuật chia để trị (D&C) để giảm bớt thao tác tính dp[i][j].

Giả định chúng ta đã có được vị trí k cho dp[i][j], vì tính đơn điều của opt, chúng ta biết được với một vị trí a < j thì opt(i, a) <= opt(i, j), và với vị trí b >j thì opt(i, b)>= opt(i, j).

Dựa vào điều này, chúng ta điền giá trị trên mỗi hàng thứ i bằng cách chia đôi dần. Đầu tiên tính dp[i. M/2] bằng cách duyệt k nguyên hàng đó, lưu lại opt(i, M/2). Sau đó tính dp(i, M/4) chỉ cần duyệt k từ i đến opt(i, M/2) đồng thời tính dp(i, 3M/4) chỉ cần duyệt k từ opt(i, M/2) đến N. Cứ như vậy đến khi điền xong nguyên một hàng.

Các em tham khảo đoạn code sau:

// Function to perform the decide and conquer

void divide(int l, int r, int optl, int optr, int i)

{

if (l > r)

return;

// Find middle value

int mid = (l + r) >> 1;

// Store the minimum cost and opt(i, j)

pair<int, int> best = { INT_MAX, -1 };

// Find the value of the best cost and opt(i, j)

for (int k = optl; k < min(mid, optr); k++)

best = min(

best,

{ (k ? dp[i - 1][k] : 0) + cost[k][mid], k });

// Store the minimum cost in the dp array

dp[i][mid] = best.first;

int opt = best.second;

// Recursively call the divide function

// to fill the other dp states

divide(l, mid - 1, optl, opt, i);

divide(mid + 1, r, opt, optr, i);

}

void solve()

{

// Initial state of the dp table

// Normally table is initialized for j=0

// or j=1 depending on problem statement

for (int i = 0; i < N; i++)

dp[0][i] = cost[0][i];

// Fill in the dp array

// with the divide function

for (int i = 1; i < M; i++)

divide(0, N - 1, 0, N - 1, i);

cout << dp[M - 1][N - 1] << endl;

}

Nguồn: GeeksforGeeks

Độ phức tạp: O(M*NlogN)

Làm sao chứng minh opt(i, j) ≤ opt(i, j +1)

Đây là phần khó nhất trong kỹ thuật này. Tuy nhiên, người ta chứng minh được rằng nếu hàm cost(i, j) thỏa bất đẳng thức tứ giác thì điều kiện đơn điệu của opt(i, j) sẽ được đảm bảo (nhưng chiều ngược lại là không chắc).

Bất đẳng thức tứ giác (quadrangle inequality ) :

cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c) for all a ≤ b ≤ c ≤ d.

Việc kiểm tra được hàm cost thỏa bất đẳng thức tứ giác tùy thuộc vào tính chất từng bài.

Đối với bài này có thể dựa vào cách mô tả cost là tổng bình phương của một đoạn cùng cách chúng ta tính bằng mảng cộng dồn, chúng ta có thể đặt lại các biến như sau:

x = sum(b, c) ; y = sum(a, c) − sum(b, c); z = sum(b, d) − sum(b, c). với sum(p, q) là tổng các giá trị trong khoản từ p đến q. lúc này bất đẳng thức tứ giác trở thành:

(x + y)2 + (x + z)2 ≤ (x + y + z)2 + x2

⇔ 0 ≤ 2yz, với y và z không âm, bất đẳng thức bên cạnh đúng => bất đẳng thức thỏa mãn. (Nguồn: GeeksforGeeks)

Một dạng cost function có dạng tương tự như cost function trên cũng thỏa được bất đẳng thức tứ giác là:

Bài toán thứ 2

Cho một mảng A[1..M] chứa M số nguyên, định nghĩa cost(k, j) với k ≤ j là số cặp nghịch thế (cặp mà với i < j mà A[i] > A[j]). Cho một số nguyên N, hãy tìm cách chia A thành N dãy con sao cho tổng số cặp nghịch thế trên toàn bộ các dãy con là nhỏ nhất.

Nguồn: Steven Halim, CP4, page 562

Bài toán thứ 3

Cho một dãy số A bao gồm N số nguyên, yêu cầu hãy chia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các số ở phần bên phải. Với mỗi bước như vậy bạn được 1 điểm còn nếu không thể chia được thì trò chơi sẽ kết thúc. Sau khi chia thành công bạn sẽ được chọn dãy số bên trái hoặc bên phải để tiếp tục cuộc chơi với các bước như trên cho đến khi trò chơi kết thúc.

Yêu cầu: Tính xem số điểm lớn nhất có thể đạt được là bao nhiêu theo cách chia trên.

Dữ liệu

Dòng đầu tiên ghi một số nguyên T (1 ≤ T ≤ 10) là số lượng bộ dữ liệu. Mỗi bộ liệu bao gồm hai dòng:

Dòng đầu tiên ghi một số nguyên N là số lượng phần tử của dãy A.

Dòng thứ hai gồm N phần tử của dãy A được ghi cách nhau bởi dấu cách (0 ≤ ai ≤ 109).

Kết quả

Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu đó.

Ví dụ:

Input:

3 3 3

2 2 2 2

4 1 0 1 1 0 1

Output:

Ràng buộc

30% số bộ dữ liệu có N≤ 200.
60% số bộ dữ liệu có N≤ 2000.
100% số bộ dữ liệu có N≤ 20000.

Nguồn bài: Tài liệu chuyên đề, đại học CNTT, Đại học Quốc Gia TP.HCM, thông qua studocu.vn

Phân tích:

Điều kiện có điểm của một lần chia ở đây là tổng bên trái bằng tổng bên phải. Tổng điểm có được lúc này bằng 1 + max(điểm đạt được bên trái, điểm đạt được bên phải). Quá trình này làm tương tự cho bên trái, phải nên tự thân cách tính theo mô tả của đề bài đã chỉ ra cách đệ quy. Và cost function trong trường hợp này là:

Bây giờ, ta cần một bảng DP lưu điểm tối đa đạt được mỗi bước:

Vậy ta cần tìm ra điểm chia k nhanh nhất có thể.

Sử dụng prefix sum để tính trước tổng cộng dồn trên mảng đã cho
Sử dụng Binary search để tìm vị trí k

Một số bài toán khác

Contest luyện tập

Nhiệm vụ: Thực hiện contest ngắn - Luyện tập quy hoạch động chia để trị - D&C DP

Page updated

Google Sites

Report abuse