Quy hoạch động trên đoạn

Mức độ: Nâng cao

Nhiều bài có dạng: một dãy được gộp dần các phần tử cạnh nhau (gộp đá, nhân ma trận), hoặc bị lấy dần từ hai đầu, hoặc hỏi về xâu đối xứng. Kết quả của cả dãy phụ thuộc vào kết quả của các đoạn con liên tiếp. Quy hoạch động trên đoạn lưu đáp số cho mọi đoạn con [l, r] trong bảng dp[l][r], rồi tính đoạn dài từ các đoạn ngắn hơn.

Bài mẫu: gộp đá

Có n đống đá xếp thành hàng, đống thứ i có a_i viên. Mỗi lần gộp hai đống cạnh nhau thành một đống, tốn số tiền bằng tổng số viên của hai đống. Gộp tới khi còn một đống. Tổng chi phí nhỏ nhất là bao nhiêu?

Khác bài nối dây (gộp hai đoạn bất kỳ, tham lam được): ở đây chỉ được gộp hai đống cạnh nhau, nên gộp hai đống nhỏ nhất trước có thể không làm được hoặc làm hỏng các bước sau.

Nhìn vào bước cuối cùng. Lần gộp cuối cùng ghép hai đống: một đống gồm các đống ban đầu từ l tới k, một đống gồm các đống từ k + 1 tới r. Hai nửa đó được gộp độc lập với nhau, mỗi nửa nên gộp với chi phí nhỏ nhất. Lần gộp cuối tốn đúng tổng số viên của cả đoạn, không phụ thuộc cách gộp trước đó. Vậy

dp[l][r] = min theo k (l ≤ k < r) của dp[l][k] + dp[k + 1][r] + (tổng a_l đến a_r),

với dp[i][i] = 0 (một đống thì không cần gộp). Tổng đoạn tính nhanh bằng tổng tiền tố.

Thứ tự tính. dp[l][r] cần các đoạn ngắn hơn, nên tính theo độ dài đoạn tăng dần: độ dài 1, rồi 2, rồi 3…

Với 4 đống 1 3 2 4 (tổng các đoạn: [1, 2] là 4, [2, 3] là 5, [3, 4] là 6, [1, 3] là 6, [2, 4] là 9, cả dãy là 10):

Đoạn	Các cách chia ở k	dp
1 3	0 + 0 + 4	4
3 2	0 + 0 + 5	5
2 4	0 + 0 + 6	6
1 3 2	(1)(3 2): 0 + 5 + 6 = 11; (1 3)(2): 4 + 0 + 6 = 10	10
3 2 4	(3)(2 4): 0 + 6 + 9 = 15; (3 2)(4): 5 + 0 + 9 = 14	14
1 3 2 4	(1)(3 2 4): 14 + 10 = 24; (1 3)(2 4): 4 + 6 + 10 = 20; (1 3 2)(4): 10 + 10 = 20	20

Python

import sys
d = sys.stdin.read().split()
n = int(d[0])
a = list(map(int, d[1:1 + n]))
tien_to = [0] * (n + 1)
for i in range(n):
    tien_to[i + 1] = tien_to[i] + a[i]
dp = [[0] * n for _ in range(n)]
for do_dai in range(2, n + 1):
    for l in range(n - do_dai + 1):
        r = l + do_dai - 1
        dp[l][r] = min(dp[l][k] + dp[k + 1][r] for k in range(l, r)) + tien_to[r + 1] - tien_to[l]
print(dp[0][n - 1])

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), tienTo(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        tienTo[i + 1] = tienTo[i] + a[i];
    }
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for (int doDai = 2; doDai <= n; doDai++)
        for (int l = 0; l + doDai - 1 < n; l++) {
            int r = l + doDai - 1;
            dp[l][r] = LLONG_MAX;
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            dp[l][r] += tienTo[r + 1] - tienTo[l];
        }
    cout << dp[0][n - 1] << "\n";
    return 0;
}

Có khoảng n² / 2 đoạn, mỗi đoạn thử tới n điểm chia, nên số bước khoảng n³ / 6. Với n = 300 là khoảng 4,5 × 10⁶ bước. Giới hạn n vài trăm trong đề là dấu hiệu thường gặp của dạng này.

Hai kiểu chuyển trạng thái

Hầu hết các bài quy hoạch động trên đoạn thuộc một trong hai kiểu:

Kiểu	Ý nghĩa	Ví dụ
chia ở k	đoạn [l, r] được ghép từ [l, k] và [k + 1, r]	gộp đá, nhân chuỗi ma trận, cắt gậy
xử lý hai đầu	chỉ xét al và ar, đi về [l + 1, r] hoặc [l, r - 1] hoặc [l + 1, r - 1]	xâu đối xứng, lấy số từ hai đầu

Kiểu thứ hai chỉ có 3 lựa chọn cho mỗi đoạn, nên chỉ mất khoảng n² bước, dùng được với n tới vài nghìn.

Kiểu xử lý hai đầu: dãy con đối xứng dài nhất

Cho xâu s, tìm dãy con (xóa bớt ký tự, giữ thứ tự) đọc xuôi ngược như nhau dài nhất. Gọi dp[l][r] là đáp số cho đoạn s[l..r]:

• nếu s[l] = s[r] thì lấy cả hai ký tự làm hai đầu: dp[l][r] = dp[l + 1][r - 1] + 2;
• ngược lại một trong hai ký tự không được dùng: dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]).

Với xâu bcbab: đáp số là 3 (ví dụ bcb hoặc bab).

dp[l][r] chỉ cần hàng l + 1, nên khi tính l từ n - 1 về 0 chỉ cần giữ hai hàng, đỡ tốn bộ nhớ khi n lớn:

Python

s = input().strip()
n = len(s)
hang_sau = [0] * n                 # dp[l + 1][...]
for l in range(n - 1, -1, -1):
    hang = [0] * n                 # dp[l][...]
    hang[l] = 1
    for r in range(l + 1, n):
        if s[l] == s[r]:
            hang[r] = hang_sau[r - 1] + 2
        else:
            hang[r] = max(hang_sau[r], hang[r - 1])
    hang_sau = hang
print(hang_sau[n - 1])

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> hangSau(n, 0), hang(n, 0);
    for (int l = n - 1; l >= 0; l--) {
        hang.assign(n, 0);
        hang[l] = 1;
        for (int r = l + 1; r < n; r++) {
            if (s[l] == s[r]) hang[r] = hangSau[r - 1] + 2;
            else hang[r] = max(hangSau[r], hang[r - 1]);
        }
        swap(hang, hangSau);
    }
    cout << hangSau[n - 1] << "\n";
    return 0;
}

Khi l + 1 > r - 1 (hai ký tự cạnh nhau), hang_sau[r - 1] là dp[l + 1][l], một đoạn rỗng, có giá trị 0 đúng như mong muốn.

Mẹo: chọn phần tử xử lý cuối cùng

Có bài mà nghĩ theo “bước đầu tiên” thì hai phần còn lại không độc lập. Ví dụ bắn bóng bay: bắn quả bóng i được a_trái × a_i × a_phải điểm, với trái, phải là hai quả còn lại sát bên. Nếu chọn quả bắn đầu tiên là k, thì sau đó hai quả hai bên k trở thành hàng xóm, hai phía dính vào nhau.

Chọn quả bắn cuối cùng trong đoạn là k: trước khi bắn k, phía trái và phía phải của k bị bắn hết một cách độc lập (k chắn ở giữa), và khi bắn k thì hàng xóm của nó chính là hai quả ở ngoài đoạn. Cách nhìn “phần tử cuối cùng” này gặp rất nhiều trong dạng quy hoạch động trên đoạn.

Luyện tập

Gồm 14 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Chia đoạn ở điểm k

Bài 1. Gộp đá

Dòng đầu có n (1 ≤ n ≤ 400), dòng thứ hai có a₁, …, a_n (1 ≤ a_i ≤ 10⁹): số viên đá của n đống xếp thành hàng. Mỗi lần gộp hai đống cạnh nhau thành một đống, tốn số tiền bằng tổng số viên của hai đống. In ra tổng chi phí nhỏ nhất để gộp thành một đống.

Ví dụ:

Nhập	In ra
4 1 3 2 4	20

Kiểm tra: nhập

7
5 2 8 1 6 3 4

Xem đáp số

79

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Gộp đá quanh hồ

Như bài 1 nhưng n đống (1 ≤ n ≤ 200) xếp thành vòng tròn quanh hồ: đống n và đống 1 cũng cạnh nhau. In ra tổng chi phí nhỏ nhất.

Ví dụ:

Nhập	In ra
4 1 9 9 1	33

Kiểm tra: nhập

6
7 1 9 2 8 3

Xem đáp số

78

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Nhân chuỗi ma trận

Dòng đầu có n (1 ≤ n ≤ 300), dòng thứ hai có n + 1 số d₀, d₁, …, d_n (1 ≤ d_i ≤ 100): ma trận thứ i có d_i-1 hàng, d_i cột. Nhân ma trận p × q với ma trận q × r tốn p × q × r phép nhân và được ma trận p × r. Cần tính tích của n ma trận theo đúng thứ tự (chỉ được chọn cách đặt ngoặc). In ra số phép nhân ít nhất.

Ví dụ:

Nhập	In ra
3 10 30 5 60	4500

Kiểm tra: nhập

6
30 35 15 5 10 20 25

Xem đáp số

15125

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Cắt gậy

Dòng đầu có L và m (2 ≤ L ≤ 10⁹, 1 ≤ m ≤ 300), dòng thứ hai có m vị trí cắt khác nhau, mỗi vị trí từ 1 đến L - 1. Một cây gậy dài L phải cắt ở đúng các vị trí đó, theo thứ tự tùy chọn. Cắt một đoạn gậy dài x tốn x đồng. In ra tổng chi phí nhỏ nhất.

Ví dụ:

Nhập	In ra
10 3 2 4 7	20

Kiểm tra: nhập

20 5
3 8 10 12 17

Xem đáp số

52

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Xâu đối xứng và dãy ngoặc

Bài 5. Dãy con đối xứng dài nhất

Một dòng có xâu s gồm chữ cái thường (1 ≤ độ dài ≤ 5000). In ra độ dài dãy con đối xứng dài nhất của s (dãy con: xóa bớt một số ký tự, giữ nguyên thứ tự các ký tự còn lại).

Ví dụ: nhập bcbab thì in ra 3.

Kiểm tra: nhập character.

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đếm xâu con đối xứng

Một dòng có xâu s gồm chữ cái thường (1 ≤ độ dài ≤ 3000). In ra số cặp (l, r) với l ≤ r mà xâu con liên tiếp s[l..r] đối xứng.

Ví dụ: nhập abaa thì in ra 6.

Kiểm tra: nhập abacabadaba.

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Chia thành ít đoạn đối xứng nhất

Một dòng có xâu s gồm chữ cái thường (1 ≤ độ dài ≤ 2000). Chia s thành các xâu con liên tiếp, mỗi xâu đều đối xứng. In ra số xâu ít nhất.

Ví dụ: nhập aabcbd thì in ra 3.

Kiểm tra: nhập abacdcabaxyx.

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Dãy ngoặc con dài nhất

Một dòng có xâu s gồm các ký tự (, ), [, ] (1 ≤ độ dài ≤ 300). In ra độ dài dãy con dài nhất của s (xóa bớt ký tự, giữ thứ tự) là một dãy ngoặc đúng.

Ví dụ: nhập ([)] thì in ra 2.

Kiểm tra: nhập ([]])[(()]).

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Phần tử xử lý cuối cùng

Bài 9. Bắn bóng bay

Dòng đầu có n (1 ≤ n ≤ 300), dòng thứ hai có a₁, …, a_n (1 ≤ a_i ≤ 100): số ghi trên n quả bóng xếp hàng. Bắn một quả được tích số của nó với hai quả còn lại sát bên trái và bên phải (bên nào không còn bóng thì coi là số 1), rồi quả đó biến mất. Bắn hết các quả. In ra tổng điểm lớn nhất.

Ví dụ:

Nhập	In ra
4 3 1 5 8	167

Kiểm tra: nhập

7
2 7 1 9 4 3 6

Xem đáp số

831

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Chia đa giác thành tam giác

Dòng đầu có n (3 ≤ n ≤ 300), dòng thứ hai có w₀, …, w_n-1 (1 ≤ w_i ≤ 100): số ghi ở n đỉnh của một đa giác lồi theo thứ tự. Kẻ các đường chéo không cắt nhau để chia đa giác thành n - 2 tam giác. Mỗi tam giác có giá trị bằng tích ba số ở ba đỉnh. In ra tổng giá trị nhỏ nhất của các tam giác.

Ví dụ:

Nhập	In ra
4 3 7 4 5	144

Kiểm tra: nhập

7
1 3 1 4 1 5 2

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Máy in kỳ lạ

Một dòng có xâu s gồm chữ cái thường (1 ≤ độ dài ≤ 100). Một máy in mỗi lượt in một đoạn liên tiếp toàn cùng một chữ cái, chữ mới đè lên chữ cũ. Lúc đầu giấy trắng. In ra số lượt ít nhất để in được đúng xâu s.

Ví dụ: nhập aba thì in ra 2.

Kiểm tra: nhập abcabcba.

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đặt ngoặc cho biểu thức

Một dòng có biểu thức gồm các chữ số 0 đến 9 xen kẽ với dấu + hoặc *, không có dấu cách (có từ 1 đến 15 chữ số). Đặt thêm ngoặc tùy ý để giá trị biểu thức lớn nhất. In ra giá trị đó.

Ví dụ: nhập 1+2*3+4 thì in ra 21.

Kiểm tra: nhập 2*1+3*1+2*2+1.

Xem đáp số

72

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 13. Lấy số ở hai đầu

Dòng đầu có n (1 ≤ n ≤ 3000), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Hai bạn An và Bình lần lượt lấy một số ở đầu trái hoặc đầu phải của dãy, An đi trước, tới khi hết số. Mỗi bạn được tổng các số mình lấy, và cả hai đều chơi tốt nhất để hiệu số (điểm mình trừ điểm bạn kia) lớn nhất. In ra điểm của An trừ điểm của Bình.

Ví dụ:

Nhập	In ra
4 4 7 2 9	10

Kiểm tra: nhập

8
3 9 1 2 8 6 7 4

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Gộp hai số bằng nhau

Dòng đầu có n (1 ≤ n ≤ 500), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 1000). Mỗi lần được chọn hai số cạnh nhau và bằng nhau, cùng bằng x, thay cả hai bằng một số x + 1. In ra độ dài nhỏ nhất của dãy sau khi gộp nhiều lần tùy ý.

Ví dụ:

Nhập	In ra
5 4 3 2 2 3	2

Kiểm tra: nhập

9
2 1 1 3 2 2 2 4 3

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.