Quy Tắc Bất Đẳng Thức Tứ Giác

Tổng Quan Cơ Bản

Bất đẳng thức tứ giác là một kỹ thuật tối ưu hóa dựa trên tính đơn điệu, thường được kết hợp với phương pháp quy hoạch động để giải quyết các bài toán hiệu quả hơn.

Ví Dụ: Kết Hợp Đá

Xem xét một bài toán cổ điển:

Có N đống đá được xếp xung quanh một sân hình tròn. Nhiệm vụ là kết hợp các đống đá này thành một đống duy nhất theo thứ tự. Mỗi lần chỉ được chọn hai đống liền kề để hợp nhất, và số lượng đá của đống mới được tính là điểm số của lần hợp nhất đó. Hãy thiết kế một thuật toán để tính điểm số tối thiểu khi hợp nhất tất cả các đống đá thành một.

Giải Pháp Trực Tiếp

Đây là một bài toán quy hoạch động trên đoạn kinh điển.

Sau khi phá vỡ vòng tròn thành một chuỗi, ta định nghĩa \(dp[i][j]\) là điểm số tối ưu cho đoạn từ i đến j. Công thức sẽ là:

$dp(l,r) = \min\limits_{l \le k \le r}(dp(l,k)+dp(k+1, r)))+w(l, r)) $

Cách tiếp cận trực tiếp này có n2 trạng thái, và mỗi trạng thái cần O(n) để duyệt, do đó độ phức tạp là O(n3). Để tiện cho việc so sánh sau này, chúng ta viết mã như sau:

for(int i = n*2-1; i >= 1; i--){
    for(int j = i+1; j < n*2; j++){
        for(int k = i; k < j; k++)
            if(f[i][k] + f[k+1][j] + sum[j] - sum[i-1] < f[i][j]){
                f[i][j] = f[i][k] + f[k+1][j] + sum[j] - sum[i-1]; 
            }
    }
}

Khám Phá Bất Đẳng Thức Tứ Giác - Qua Quá Trình Áp Dụng

Để tối ưu hóa bài toán này, chúng ta sử dụng bất đẳng thức tứ giác điển hình.

Chúng ta sẽ đi qua quá trình giải quyết bài toán, tạm thời bỏ qua các phần chứng minh.

Đối với bốn điểm trên một chuỗi \(l, l', r', r\), nếu thỏa mãn hai tính chất sau:

① Tính đơn điệu của đoạn: Nếu \(l \leq l' \leq r' \leq r\), thì \(w(l', j') \leq w(l, r)\)

Tính chất này thường dễ nhận biết và thường được thỏa mãn trong hầu hết các trường hợp, vì vậy các tài liệu hướng dẫn thường không đề cập nhiều đến nó.

② Bất đẳng thức tứ giác: Nếu \(l \leq l' \leq r' \leq r\), thì \(w(l,r')+w(l',r) \leq w(l',r')+w(l,r)\)

Chúng ta có thể hình dung bốn đoạn này như hai đoạn thẳng, trường hợp đoạn thẳng cắt nhau tối ưu hơn trường hợp một đoạn chứa đoạn kia. Tên gọi "bất đẳng thức tứ giác" có lẽ bắt nguồn từ đây.

Xem xét công thức của chúng ta: $dp(l,r) = \min\limits_{l \le k \le r}(dp(l,k)+dp(k+1, r)))+w(l, r)) $

Chỉ cần \(w(l,r)\) thỏa mãn tính chất này, ta có hai kết luận quan trọng:

① \(dp(l,r)\) cũng thỏa mãn bất đẳng thức tứ giác

② Nếu điểm quyết định tối ưu của \(dp(l,r)\) là m, thì m nằm giữa các điểm quyết định tối ưu của \(dp(l,r-1)\) và \(dp(l+1,r)\)

Tức là \(m(l,r-1) \leq m(l,r) \leq m(l+1,r)\

Hiểu điều này trên ma trận sẽ dễ hình dung hơn.

Điểm mấu chốt nằm ở kết luận thứ hai, vì nó ảnh hưởng trực tiếp đến phạm vi vòng lặp của k!

Chúng ta hãy hoàn thiện mã:

for(int i = 1; i < 2*n; i++)
    m[i][i] = i; // Khởi tạo
for(int i = n*2-1; i >= 1; i--){
    for(int j = i+1; j < n*2; j++){
        for(int k = m[i][j-1]; k <= m[i+1][j]; k++)
            if(f[i][k] + f[k+1][j] + sum[j] - sum[i-1] > f[i][j]){
                f[i][j] = f[i][k] + f[k+1][j] + sum[j] - sum[i-1]; 
                m[i][j] = k; // Ghi lại điểm quyết định
            }
    }
}

Vấn đề đã được giải quyết.

Quá Trình Chứng Minh

Quá trình đơn giản, nhưng tại sao chúng ta có thể suy luận như vậy?

Làm thế nào để đảm bảo dp(i,j) thỏa mãn bất đẳng thức tứ giác? Có thể thay thế giá trị nhỏ nhất bằng giá trị lớn nhất không?

Tùy thuộc vào từng trường hợp, chúng ta sẽ có các cách chứng minh khác nhau.

Chúng ta xét trường hợp \(l \le l' \le r' \le r\).

Trường hợp 1: Khi \(l' = l\)

Khi \(l' = l\), quá trình chứng minh như sau:

\(dp(l,r') + dp(l',r) = dp(l,r') + dp(l,r)\) (vì \(l' = l\))

Lại vì \(l = l'\), nên:

\(dp(l',r') + dp(l,r) = dp(l,r') + dp(l,r)\).

Do đó, mệnh đề được chứng minh, hoàn tất.

Trường hợp 2: Khi \(r' = r\)

Tương tự như trường hợp \(l' = l\), không cần trình bày thêm.

Trường hợp 3: Khi \(l' = r'\)

Theo định nghĩa của \(dp\), khi \(l' = r'\), ta có \(dp(l',r')=0\), do đó:

\(dp(l,r) + dp(l',r') = dp(l,r) + 0 = dp(l,r)\).

Suy ra \(dp(l,r) = dp(l,r) + dp(l',r')\), mệnh đề được chứng minh, hoàn tất.

Trường hợp 4: Khi \(l' = r' \le k\), trong đó \(k = opt(l,r)\)

Lúc này chúng ta kết hợp phương pháp quy nạp toán học.

1. Bước 1: Chứng minh khi \(r = r'\) thì mệnh đề đúng. Điều này đã được chứng minh trong trường hợp \(r' = r\).
2. Bước 2: Giả sử khi \(r \ge r'\) thì mệnh đề đúng, suy ra \(P(\{x|x>r\})\) cũng đúng. Vì \(r' \le k < r\), có thể biến đổi bước 2 thành: giả sử \(P(k)\) đúng, suy ra mệnh đề đúng.

Nghĩa là chúng ta có giả thiết sau:

\(dp(l,r') + dp(l',k) \le dp(l,k) + dp(l',r')\.

Dưới giả thiết này, chúng ta có thể chứng minh:

\(dp(l,r') + dp(l',r) \le dp(l,r') + dp(l',k) + dp(k+1,r) + c(l',r)\)

\(\le dp(l,r') + dp(l',k) + dp(k+1,r) + c(l,r)\) (do tính đơn điệu của c)

\(\le dp(l,k) + dp(l',r') + dp(k+1,r) + c(l,r)\) (theo giả thiết)

\(= dp(l,k) + 0 + dp(k+1,r) + c(l,r)\) (theo định nghĩa \(dp\))

\(= dp(l,r)\) (theo công thức (1))

\(= dp(l,r) + dp(l',r')\) (theo công thức (2))

Chứng minh hoàn tất.

Khi \(k < l' = r'\)

Tương tự như trên, sử dụng quy nạp toán học (đổi tham số từ \(r\) sang \(l\), tức là mệnh đề \(P(l)\)).

1. Bước 1: Chứng minh khi \(l = l'\) thì \(P(l)\) đúng, điều này đã được chứng minh trong trường hợp \(l' = l\).
2. Bước 2: Giả sử khi \(l \le l'\) thì \(P(l)\) đúng, suy ra \(P(\{x|x<l\})\) cũng đúng. Vì \(l \le k < l'\), nên có thể biến đổi bước 2 thành: giả sử \(P(k+1)\) đúng, suy ra \(P(l)\) đúng.

Có giả thiết sau:

\(dp(k+1,r') + dp(l',r) \le dp(k+1,r) + dp(l',r')\.

Dưới giả thiết này, ta có:

\(dp(l,r') + dp(l',r) \le c(l,r') + dp(l,k) + dp(k+1,r') + dp(l',r)\)

\(\le c(l,r) + dp(l,k) + dp(k+1,r') + dp(l',r)\) (do tính đơn điệu của c)

\(\le c(l,r) + dp(l,k) + dp(k+1,r) + dp(l',r')\) (theo giả thiết)

\(\le c(l,r) + dp(l,k) + dp(k+1,r) + 0\) (theo định nghĩa \(dp\))

\(= dp(l,r)\) (theo công thức (1))

\(= dp(l,r) + dp(l',r')\) (theo công thức (2))

Chứng minh hoàn tất.

Khi l < l' < r' < r

Gọi \(x = opt(l,r)\), \(y = opt(l',r')\).

Theo định nghĩa của \(opt\), ta có: \(l \le x < r\), \(l' \le y < r'\).

Trường hợp 1: \(y < x\)

Lúc này có \(l < l' \le y < r'\), \(x < r\). Do đó \(l \le y < r'\), \(l' < x < r\). Từ hệ quả (1) suy ra:

\(dp(l,r') \le dp(l,y) + dp(y+1,r') + c(l,r')\)

\(dp(l',r) \le dp(l',x) + dp(x+1,r) + c(l',r)\).

Sử dụng quy nạp toán học để chứng minh mệnh đề \(P(r')\).

1. Khi \(r' = l'\) thì \(P(r')\) đúng, điều này đã được chứng minh trong trường hợp \(l' = r'\).
2. Giả sử khi \(r' \ge l'\) thì \(P(r')\) đúng, suy ra \(P(\{x|x>r'\})\) cũng đúng. Vì \(r' > y \ge l'\), nên có thể biến đổi bước 2 thành: giả sử \(P(y)\) đúng, suy ra \(P(r')\) đúng. Và vì \(x > y\), nên có giả thiết:

\(dp(l,y) + dp(l',x) \le dp(l',y) + dp(l,x)\.

Dưới giả thiết này, ta có thể chứng minh:

\(dp(l,r') + dp(l',r) \le dp(l,y) + dp(y+1,r') + c(l,r') + dp(l',x) + dp(x+1,r) + c(l',r)\)

\(\le dp(l,y) + dp(y+1,r') + c(l',r') + dp(l',x) + dp(x+1,r) + c(l,r)\) (do bất đẳng thức của c)

\(\le dp(l',y) + dp(y+1,r') + c(l',r') + dp(l,x) + dp(x+1,r) + c(l,r)\) (theo giả thiết)

\(= dp(l',r') + dp(l,r)\) (theo công thức (1))

Chứng minh hoàn tất.

Trường hợp 2: \(x \le y\)

Có \(l \le x, l' \le y < r' < r\), nên \(l \le x < r', l' \le y < r\). Từ hệ quả (1) suy ra:

\(dp(l,r') \le dp(l,x) + dp(x+1,r') + c(l,r')\)

\(dp(l',r) \le dp(l',y) + dp(y+1,r) + c(l',r)\).

Lại có \(x+1 \le y+1 < r' < r\), qua quy nạp toán học ta có giả thiết:

\(dp(x+1,r') + dp(y+1,r) \le dp(x+1,r) + dp(y+1,r')\.

Dưới giả thiết này, ta có thể chứng minh:

\(dp(l,r') + dp(l',r) \le dp(l,x) + dp(x+1,r') + c(l,r') + dp(l',y) + dp(y+1,r) + c(l',r)\)

\(\le dp(l,x) + dp(x+1,r') + c(l,r) + dp(l',y) + dp(y+1,r) + c(l',r')\) (do bất đẳng thức của c)

\(\le dp(l,x) + dp(x+1,r) + c(l,r) + dp(l',y) + dp(y+1,r') + c(l',r')\) (theo giả thiết)

\(= dp(l,r) + dp(l',r')\) (theo công thức (1))

Chứng minh hoàn tất.

Tại sao nếu w(l,r) thỏa mãn bất đẳng thức tứ giác thì có suy ra kết luận: nếu điểm quyết định tối ưu của dp(l,r) là m, thì m nằm giữa các điểm quyết định tối ưu của dp(l,r-1) và dp(l+1,r), tức là \(m(l,r-1) \leq m(l,r) \leq m(l+1,r)\)?

Nếu \(dp\) thỏa mãn bất đẳng thức tứ giác, thì \(m\) có tính đơn điệu, tức là \(m(l,r-1) \le m(l,r) \le m(l+1,r)\)

Chứng minh

Gọi \(x = m(l,r-1)\), \(y = m(l,r)\), \(z = m(l+1,r)\), ta có các bất đẳng thức sau: \(l \le x < r-1\), \(l \le y < r\), \(l+1 \le z < r\)

Chúng ta dùng phản chứng để chứng minh:

1. Nếu \(y < x\), kết hợp với các bất đẳng thức trên ta có \(y+1 < x+1 \le r-1 < r\)

Theo bất đẳng thức tứ giác, ta có: \(dp(y+1,r-1)+dp(x+1,r)\le dp(y+1,r)+dp(x+1,r-1)\)

Lại vì \(y\) là điểm quyết định tối ưu của \(dp(l,r)\), nên: \(dp(l,y)+dp(y+1,r)\le dp(l,x)+dp(x+1,r)\)

Cộng hai vế của hai bất đẳng thức trên, loại bỏ các số hạng giống nhau, ta được: \(dp(l,y)+dp(y+1,r-1)\le dp(l,x)+dp(x+1,r-1)\)

Bất đẳng thức này có nghĩa là với \(dp(l,r-1)\) thì \(y\) tốt hơn \(x\), mâu thuẫn với giả thiết ban đầu rằng \(x\) là điểm quyết định tối ưu của \(dp(l,r-1)\).

Do đó, \(x > y\) không đúng, nên \(x \le y\), tức là \(m(l,r-1) \le m(l,r)\). 2. Nếu \(z < y\), kết hợp với các bất đẳng thức trên ta có: \(l < l+1 \le z < y\)

Theo bất đẳng thức tứ giác, ta có: \(dp(l,z)+dp(l+1,y)\le dp(l,y)+dp(l+1,z)\)

Lại vì \(z\) là điểm quyết định tối ưu của \(dp(l+1,r)\), nên: \(dp(l+1,z)+dp(z+1,r)\le dp(l+1,y)+dp(y+1,r)\)

Cộng hai vế của hai bất đẳng thức trên, loại bỏ các số hạng giống nhau, ta được: \(dp(l,z)+dp(z+1,r)\le dp(l,y)+dp(y+1,r)\)

Bất đẳng thức này có nghĩa là với \(dp(l,r)\) thì \(z\) tốt hơn \(y\), mâu thuẫn với giả thiết ban đầu rằng \(y\) là điểm quyết định tối ưu của \(dp(l,r)\).

Do đó, \(y > z\) không đúng, nên \(y \le z\), tức là \(m(l,r) \le m(l+1,r)\).

Tóm lại, ta có: \(m(l,r-1) \le m(l,r) \le m(l+1,r)m(l,r-1) \le m(l,r) \le m(l+1,r)\)

Chứng minh hoàn tất.

Ví dụ 1: CF321E

Ciel và Gondolas

Mô tả bài toán

Ciel cáo đang xếp hàng chờ lên tàu đùa ở công viên giải trí. Hiện có \(n\) người trong hàng, có \(k\) chiếc thuyền, khi chiếc thuyền thứ i đến, \(q_{i}\) người đầu tiên có thể lên thuyền. Chiếc thuyền cuối cùng sẽ chở tất cả những người còn lại, do đó \(q{k}\) là số người được chở bởi chiếc thuyền này. Mọi người không muốn đi cùng người lạ trên cùng một chiếc thuyền, khi người thứ i và người thứ j cùng trên một chiếc thuyền, sẽ gây ra sự khó chịu với giá trị \(u_{i,j}\). Hãy tính tổng giá trị khó chịu tối thiểu. Mỗi cặp người trên cùng một chiếc thuyền đều gây ra sự khó chịu.

Định dạng đầu vào:

Hai số nguyên đầu tiên đại diện cho \(n\) và \(k\), tiếp theo là \(n\) hàng mỗi hàng \(n\) số, số thứ i của hàng thứ j đại diện cho \(u_{i,j}\). Sử dụng kỹ thuật đọc nhanh để tránh TLE do đọc dữ liệu.

Định dạng đầu ra:

Một số nguyên duy nhất đại diện cho tổng giá trị khó chịu tối thiểu.

Ví dụ #1

Đầu vào mẫu #1

5 2
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0

Đầu ra mẫu #1

0

Ví dụ #2

Đầu vào mẫu #2

8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

Đầu ra mẫu #2

7

Ví dụ #3

Đầu vào mẫu #3

3 2
0 2 0
2 0 3
0 3 0

Đầu ra mẫu #3

2

Gợi ý

Trong ví dụ đầu tiên, chúng ta có thể phân bổ người như sau: {1, 2} lên một chiếc gondola, {3, 4, 5} lên chiếc gondola còn lại.

Trong ví dụ thứ hai, một giải pháp tối ưu là: {1, 2, 3} | {4, 5, 6} | {7, 8}.

Rõ ràng, chúng ta có thể áp dụng khuôn mẫu quy hoạch động chia cắt: \(dp[i][j]=\min\limits_{1\le k\lt j}(dp[i-1][k]) + w(k,j)\)

\(w(l,r)\) thực chất là tổng hai chiều trước, tạo một bảng và ta thấy nó thỏa mãn bất đẳng thức tứ giác... (thực tế tổng trước luôn có tính chất này)

Vậy nên...

dp[0][0] = 0;
for (int i = 1; i <= K; i++)
    for (int j = N; j >= 1; j--){
        for (int k = m[i - 1][j]; k <= m[i][j + 1]; k++)
            if (dp[i][j] > dp[i - 1][k - 1] + cal(k, j)){
                dp[i][j] = dp[i - 1][k - 1] + cal(k, j);
                m[i][j] = k;
            }
    }

Đừng quên đọc dữ liệu nhanh.

Ví dụ 2. [NOI2009] Nhà thơ nhỏ G

Mô tả bài toán

Nhà thơ nhỏ G là một nhà thơ tài ba, thường tự sáng tác thơ để giải trí. Nhưng anh ấy luôn bị một vấn đề làm phiền, đó là vấn đề sắp xếp thơ.

Một bài thơ bao gồm nhiều câu, một số câu liên tiếp có thể được ngăn cách bằng dấu cách và đặt trên cùng một dòng, lưu ý rằng số câu có thể đặt trên một dòng không bị giới hạn. Nhà thơ G định nghĩa một độ dài chuẩn cho mỗi bài thơ (độ dài của một dòng là tổng số ký tự trong dòng đó), anh ấy mong muốn sau khi sắp xếp, độ dài mỗi dòng không chênh lệch quá nhiều so với độ dài chuẩn. Rõ ràng khi sắp xếp, không được thay đổi thứ tự các câu có sẵn, và nhà thơ G không cho phép chia một câu thành nhiều dòng. Trong hai điều kiện trên, nhà thơ G định nghĩa một sự không hài hòa cho mỗi dòng là giá trị tuyệt đối của hiệu giữa độ dài thực tế và độ dài chuẩn, lũy thừa bậc \(P\), và sự không hài hòa tổng của cả bài thơ là tổng sự không hài hòa của tất cả các dòng.

Nhà thơ G vừa sáng tác thêm vài bài thơ, bây giờ hãy sắp xếp bài thơ này để sự không hài hòa của bài thơ được giảm thiểu nhất, và cho anh ấy kết quả sắp xếp.

Định dạng đầu vào

Dòng đầu của tệp đầu vào là một số nguyên \(T\), biểu thị số lượng bài thơ.

Tiếp theo là \(T\) bài thơ, mỗi bài thơ là một bộ dữ liệu kiểm tra. Dòng đầu tiên của mỗi bộ dữ liệu kiểm tra là ba số nguyên dương cách nhau bởi dấu cách \(N,L,P\), trong đó: \(N\) là số câu của bài thơ, \(L\) là độ dài chuẩn của bài thơ, \(P\) được mô tả trong phần mô tả bài toán.

Từ dòng thứ hai, mỗi dòng là một câu, câu bao gồm các ký tự chữ cái, chữ số, dấu câu, v.v. (mã ASCII từ 33 đến 127, không chứa ký tự -).

Định dạng đầu ra

Đối với mỗi bộ dữ liệu kiểm tra, nếu sự không hài hòa tối thiểu không vượt quá \(10^{18}\), thì dòng đầu tiên là một số, biểu thị sự không hài hòa tối thiểu. Tiếp theo là một số dòng, biểu thị kết quả sắp xếp thơ của bạn. Lưu ý rằng giữa hai câu liền kề trên cùng một dòng cần có một dấu cách.

Nếu có nhiều giải pháp khả thi, tất cả đều có cùng giá trị sự không hài hòa tối thiểu, thì chỉ cần xuất ra một trong số chúng. Nếu sự không hài hòa tối thiểu vượt quá \(10^{18}\), thì xuất ra Too hard to arrange. Sau mỗi bộ dữ liệu kiểm tra, xuất ra --------------------, tổng cộng 20 ký tự -, mã ASCII của - là 45, không xuất thêm dòng trống hoặc khoảng trắng không cần thiết.

Ví dụ #1

Đầu vào mẫu #1

4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet

Đầu ra mẫu #1

108
brysj,
hhrhl.
yqqlm,
gsycl.
--------------------
32
brysj, hhrhl.
yqqlm, gsycl.
--------------------
Too hard to arrange
--------------------
1000000000000000000
poet
--------------------

Gợi ý

Giải thích đầu vào-đầu ra ví dụ 1

Trong hai bộ dữ liệu đầu vào, độ dài thực tế của mỗi dòng đều là \(6\), trong hai bộ dữ liệu sau, độ dài thực tế của mỗi dòng là \(4\). Trong một phương án sắp xếp, khoảng trắng giữa hai câu liền kề trên cùng một dòng cũng được tính vào độ dài của dòng đó (có thể tham khảo bộ dữ liệu thứ hai trong ví dụ). Không có khoảng trắng ở cuối dòng.

Quy mô dữ liệu và thỏa thuận

Điểm kiểm tra	\\(T\\)	\\(N\\)	\\(L\\)	\\(P\\)
\\(1\\)	\\(\\le 10\\)	\\(\\le18\\)	\\(\\le 100\\)	\\(\\le5\\)
\\(2\\)	\\(\\le 10\\)	\\(\\le 2\\times 10^3\\)	\\(\\le 6\\times 10^4\\)	\\(\\le10\\)
\\(3\\)	\\(\\le 10\\)	\\(\\le 2\\times 10^3\\)	\\(\\le 6\\times 10^4\\)	\\(\\le10\\)
\\(4\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 200\\)	\\(\\le10\\)
\\(5\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 200\\)	\\(\\le10\\)
\\(6\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 3\\times 10^6\\)	\\(2\\)
\\(7\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 3\\times 10^6\\)	\\(2\\)
\\(8\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 3\\times 10^6\\)	\\(\\le10\\)
\\(9\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 3\\times 10^6\\)	\\(\\le10\\)
\\(10\\)	\\(\\le 5\\)	\\(\\le 10^5\\)	\\(\\le 3\\times 10^6\\)	\\(\\le10\\)

Tất cả các câu đều có độ dài không vượt quá \(30\).

Rõ ràng, đây là bài toán quy hoạch động chia cắt, đặt \(f[i]\) là sự không hài hòa tối thiểu của \(i\) từ đầu tiên: \(f[i] = min(f[j]) + w(i,j)\), trong đó \(w(i,j)\) là giá trị không hài hòa khi chia từ \(i\) đến \(j\) thành một đoạn, có thể tính trực tiếp bằng tổng trước, chú ý đến chi tiết về khoảng trắng.

Nhưng độ phức tạp là \(O(n^2)\)

Đặt \(P[i]\) là điểm chia cắt tối ưu của \(f[i]\), theo tính chất trước đó, \(P[i]\) có tính đơn điệu, một tính chất mạnh hơn là: với \(i<i'\), chắc chắn có \(P[i] \le P[i']\, như vậy phạm vi duyệt mỗi lần dường như đã thay đổi từ \([1,i-1]\) thành \([p[i-1], i-1]\, nhưng sự tối ưu hóa này thực sự không hữu ích vì độ phức tạp không thay đổi, không giảm như trường hợp hai chiều trước đó.

Tuy nhiên, chúng ta vẫn có thể đạt được một giải pháp có độ phức tạp \(O(nlogn)\).

Đầu tiên, với trạng thái cuối cùng, tất cả các \(P[i]\) đều có tính đơn điệu, ví dụ như sau:

1 1 2 2 2 3 3 3 3 5 5 5 5 5 6 6 6

Như vậy, chúng ta thay đổi tư duy, khi duyệt đến \(i\), trước tiên cập nhật \(f[i]\) (cách cập nhật chúng ta sẽ bàn sau), sau đó xem xét vị trí hiện tại \(i\) nếu làm điểm cắt tối ưu thì sẽ ảnh hưởng đến bao nhiêu vị trí.

Vẫn lấy ví dụ trên, giả sử hiện tại đã duyệt đến \(i=7\), do đó tất cả các \(f[1]\) đến \(f[6]\) đã được xác định, trạng thái của toàn bộ mảng \(P\) chính là ví dụ trước:

1 1 2 2 2 3 3 3 3 5 5 5 5 5 6 6 6

Bây giờ, chúng ta xử lý \(f[7]\), rõ ràng, điểm cắt tối ưu của vị trí thứ 7 hiện tại là \(3\), tức là \(P[7]=3\), do đó có thể dùng công thức \(f[7]=f[3]+w(4,7)\) để tính \(f[7]\)

Tiếp theo, chúng ta xem xét vị trí \(7\) nếu làm điểm cắt tối ưu thì sẽ ảnh hưởng đến bao nhiêu vị trí, chúng ta nên xét ngược lại, trước tiên xem xét vị trí bên trái nhất của đoạn cuối cùng \(15\), điểm cắt tối ưu là \(6\), thay vào công thức tính giá trị tối ưu là \(f[15]=f[6]+w(7,15)\), tương tự, chúng ta cũng đưa \(7\) làm điểm cắt vào, \(f[15]=f[7]+w(8,15)\), nếu giá trị sau tốt hơn, có nghĩa là cả đoạn này sẽ được thay bằng \(7\) (do tính đơn điệu), và tiếp tục theo logic này đi lên, so sánh với mỗi vị trí bên trái. Nếu giá trị trước tốt hơn, có nghĩa là có thể chỉ có nửa sau của đoạn này sẽ được thay bằng \(7\), ví dụ:

1 1 2 2 2 3 3 3 3 5 5 5 5 5 6 7 7

Ở đây chúng ta có thể cân nhắc tìm điểm tới hạn bằng phương pháp nhị phân trong đoạn này, nhị phân một vị trí \(mid\) trong đoạn, so sánh hai giá trị \(f[mid]\) khác nhau, tức là \(f[6][mid]+w(7,mid)\) và \(f[7][mid]+w(8,mid)\).

Cách thực hiện cụ thể có thể khác nhau, cách phổ biến là sử dụng một hàng đợi kép để lưu trữ mỗi đoạn giá trị \(P\), mỗi phần tử trong hàng đợi là một bộ ba, \((x,l,r)\) biểu thị từ \(l\) đến \(r\) toàn bộ là \(x\), ban đầu toàn bộ là \(0\) hoặc \(1\), tức là \((0,1,n)\) hoặc \((1,1,n)\), sau đó tiến hành cập nhật, mỗi lần duyệt đến i, trước tiên xóa phần tử đầu hàng, xóa các đoạn không chứa i, như vậy phần tử đầu hàng chắc chắn có thể lấy được điểm cắt tối ưu của \(f[i]\) hiện tại, sau đó xóa phần tử cuối hàng theo các bước trên, cho đến khi xuất hiện trường hợp phần tử trong hàng tốt hơn, sau đó nhị phân, nhị phân xóa phần tử cuối hàng gốc \((6 6 6)\), thêm hai phần tử cuối hàng mới \((6)\), \((7 7)\).

Có nhiều chi tiết, chúc may mắn.