Quy hoạch động (4): LCS, đường đi trên lưới
- Độ khó
- ★★★★★ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Quy hoạch động (3): cái túi
- Chủ đề
- LCSquy hoạch động
- Trạng thái
Kiến thức cơ bản
Nhắc lại khuôn quy hoạch động
Mỗi bài quy hoạch động (DP) em đã làm đều có ba bước: chọn ý nghĩa của dp (trạng thái), viết công thức tính một ô từ các ô nhỏ hơn, và đặt giá trị cho các ô nhỏ nhất (cơ sở). Có những bài trạng thái cần hai chỉ số, như bài cái túi (đồ vật thứ i, sức chứa còn lại w). Tuần này, ta dùng bảng dp[i][j] cho hai kiểu bài rất hay gặp: so sánh hai xâu (dãy con chung dài nhất) và đi trên lưới. Khi gặp bài mới, hãy luôn tự hỏi trước: “dp[i][j] nghĩa là gì?”. Chọn đúng ý nghĩa của dp[i][j] là đã xong một nửa bài.
Mẫu 1: Dãy con chung dài nhất (LCS)
Dãy con của một xâu là xâu nhận được khi em xóa đi một vài ký tự (có thể không xóa) nhưng giữ nguyên thứ tự các ký tự còn lại. Ví dụ ace là dãy con của abcde, còn eca thì không. Các ký tự của dãy con không cần nằm sát nhau (khác với xâu con). Gấu Po có chuỗi hạt a, Thỏ có chuỗi hạt b. Hai bạn muốn xâu một chuỗi hạt dài nhất mà cả hai đều cắt ra được bằng cách bỏ bớt hạt. Đó là dãy con chung dài nhất, viết tắt là LCS.
Thử mọi dãy con của a sẽ phải xét 2n khả năng, với n = 2000 thì quá lớn. Ta dùng DP. Trạng thái: dp[i][j] là độ dài LCS của i ký tự đầu của a và j ký tự đầu của b. Để tính dp[i][j], em chỉ cần nhìn hai ký tự cuối của hai đoạn đó là a[i - 1] và b[j - 1] (xâu đánh số từ 0).
Nếu hai ký tự cuối giống nhau, ta ghép chúng thành một cặp, phần còn lại là LCS của i - 1 và j - 1 ký tự đầu: dp[i][j] = dp[i - 1][j - 1] + 1. Nếu hai ký tự cuối khác nhau thì ít nhất một trong hai không được dùng, ta bỏ ký tự cuối của a hoặc của b rồi chọn cách tốt hơn: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]). Cơ sở: xâu rỗng thì LCS bằng 0, tức là dp[0][j] = dp[i][0] = 0.
a = ABCBD, b = BDCB (dấu _ là xâu rỗng)
dp[i][j] = độ dài LCS của i ký tự đầu của a và j ký tự đầu của b
_ B D C B
_ 0 0 0 0 0
A 0 0 0 0 0
B 0 1 1 1 1
C 0 1 1 2 2
B 0 1 1 2 3
D 0 1 2 2 3
Ô góc dưới phải dp[5][4] = 3. Dãy con chung dài nhất là BCB.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
// dp[i][j]: LCS của i ký tự đầu của a và j ký tự đầu của b
// hàng 0 và cột 0 bằng 0 (cơ sở)
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) // hai ký tự cuối giống nhau
dp[i][j] = dp[i - 1][j - 1] + 1;
else // khác nhau: bỏ một ký tự cuối
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[n][m] << endl;
return 0;
}
Bảng có (n + 1) × (m + 1) ô, mỗi ô tính bằng vài phép so sánh nên chương trình chạy khoảng n × m phép tính. Với n = m = 2000 là 4 × 106 phép, máy chỉ mất một cái chớp mắt. Hàng 0 và cột 0 là các ô “đệm” bằng 0, nhờ đó công thức viết được cho mọi i, j ≥ 1 mà không cần xử lý riêng.
Mẫu 2: In ra dãy con chung (truy vết)
Nhiều bài không chỉ hỏi độ dài mà còn bắt in ra dãy con. Ta đi ngược từ ô dp[n][m] về góc như đi ngược một con đường. Nếu hai ký tự cuối giống nhau, ký tự đó thuộc dãy con, ta ghi lại và lùi cả i lẫn j. Nếu khác nhau, ta lùi về ô có giá trị lớn hơn (ô phía trên hoặc ô bên trái), vì dp[i][j] được lấy từ ô đó. Các ký tự được ghi theo thứ tự ngược nên cuối cùng phải đảo xâu.
string res = "";
int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) { // ký tự thuộc dãy con chung
res += a[i - 1];
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--; // dp[i][j] lấy từ ô phía trên
} else {
j--; // dp[i][j] lấy từ ô bên trái
}
}
reverse(res.begin(), res.end()); // lần ngược nên phải đảo
cout << res << endl;
Quy tắc truy vết dùng được cho mọi bài DP: muốn in nghiệm, em lần ngược xem mỗi ô được tính từ ô nào. Khi hai ô cho giá trị tốt như nhau, chọn ô nào cũng được, nên bài in nghiệm thường cho phép in một nghiệm bất kỳ.
Mẫu 3: Đếm đường đi trên lưới
Thỏ đứng ở ô (1, 1) của lưới n × m và muốn đến ô (n, m). Mỗi bước Thỏ chỉ được sang phải hoặc đi xuống. Hỏi có bao nhiêu đường đi? Bước cuối cùng của Thỏ để vào ô (i, j) chỉ có thể đi từ ô phía trên (i - 1, j) hoặc ô bên trái (i, j - 1). Hai nhóm đường này không trùng nhau nên dp[i][j] = dp[i - 1][j] + dp[i][j - 1], với dp[1][1] = 1. Nếu ô (i, j) là tường thì không đường nào đi qua nó, ta đặt dp[i][j] = 0. Hàng 0 và cột 0 toàn số 0 để các ô ngoài bảng không đóng góp đường nào.
Lưới 3 × 4 (# là tường) Bảng dp (số đường đến từng ô)
. . . . 1 1 1 1
. # . . 1 0 1 2
. . . . 1 1 2 4
Ô (2, 2) là tường nên dp = 0. Ô (2, 3): dp = 1 + 0 = 1.
Đáp án: dp[3][4] = 4 đường đi.
int n, m;
cin >> n >> m;
vector<string> g(n); // '.' đi được, '#' là tường
for (int i = 0; i < n; i++) cin >> g[i];
// dp[i][j]: số đường đi từ (1, 1) đến (i, j); hàng 0, cột 0 bằng 0
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
dp[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
if (g[i - 1][j - 1] == '#') dp[i][j] = 0; // tường
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // trên + trái
}
}
cout << dp[n][m] << endl;
Số đường đi tăng rất nhanh: lưới 30 × 30 đã có hơn 3 × 1016 đường, vượt xa int. Vì vậy em dùng long long (nhớ lại bài học tràn số).
Mẫu 4: Đường đi có tổng lớn nhất hoặc nhỏ nhất
Bây giờ mỗi ô có a[i][j] hạt dẻ. Thỏ vẫn chỉ sang phải hoặc đi xuống, nhặt hết hạt dẻ trên mọi ô đi qua. Để nhặt được nhiều nhất, tại mỗi ô ta chọn đến từ phía trên hoặc phía bên trái, tùy phía nào đã nhặt được nhiều hơn: dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1]). Đáp án là dp[n][m].
Số hạt dẻ a Bảng dp (nhiều nhất đến ô đó)
2 1 3 2 3 6
0 4 1 2 7 8
5 1 2 7 8 10
Ô (2, 2) = 4 + max(dp[1][2], dp[2][1]) = 4 + max(3, 2) = 7.
Đáp án: dp[3][3] = 10.
vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
cout << dp[n][m] << endl;
Nếu bài hỏi tổng nhỏ nhất thì đổi max thành min, nhưng phải cẩn thận với các ô ngoài bảng: chúng phải là một số rất lớn (INF), nếu để 0 thì đường đi sẽ “nhảy” vào từ ngoài bảng và cho đáp án sai. Riêng dp[0][1] = 0 để ô (1, 1) có điểm xuất phát. Muốn in đường đi, em truy vết ngược từ ô (n, m) như ở Mẫu 2: ô hiện tại được tính từ ô trên hay ô trái thì có dp nhỏ hơn.
const int INF = 1000000000;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));
dp[0][1] = 0; // ô ảo để (1, 1) có điểm xuất phát
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
Nhận dạng đề bài
| Dấu hiệu trong đề | Cách làm | Điều cần chú ý |
|---|---|---|
| Hai xâu (hoặc hai dãy), “dãy con chung”, “xóa/chèn ít nhất” | dp[i][j] trên i phần tử đầu của a và j phần tử đầu của b (LCS) | Dãy con khác xâu con; xâu đánh số từ 0 nên dùng a[i - 1] |
| Lưới, chỉ đi phải hoặc xuống, đếm số đường | dp[i][j] = dp[i - 1][j] + dp[i][j - 1], tường thì dp = 0 | Dùng long long; ô xuất phát bị tường thì đáp án 0 |
| Lưới, tổng lớn nhất hoặc nhỏ nhất | dp[i][j] = a[i][j] + max (hoặc min) của ô trên và ô trái | Tổng nhỏ nhất cần ô ngoài bảng là INF |
| Phải in nghiệm | Truy vết ngược từ dp[n][m] | Kết quả thu được theo thứ tự ngược nên phải đảo |
| Đi được cả bốn hướng, hoặc đi lại ô cũ | Không dùng DP kiểu này (dùng loang hoặc quay lui) | DP cần thứ tự rõ ràng: ô sau chỉ dựa vào ô trước |
Luyện tập
Bài 1. Chuỗi hạt chung
Gấu Po và Thỏ mỗi người có một chuỗi hạt, mỗi hạt được ghi bằng một chữ cái thường. Hai bạn muốn xâu một chuỗi hạt mới sao cho các hạt của nó xuất hiện ở cả hai chuỗi ban đầu theo đúng thứ tự (được bỏ bớt hạt nhưng không được đổi thứ tự). Chuỗi mới dài nhất có bao nhiêu hạt?
| Đầu vào | Dòng 1: xâu a. Dòng 2: xâu b. Mỗi xâu gồm từ 1 đến 2000 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một số nguyên là độ dài lớn nhất của chuỗi hạt chung. | |
| Test | Input | Output |
| 1 | abcde ace | 3 |
| 2 | abcbdab bdcaba | 4 |
| 3 | abc xyz | 0 |
Bài 2. In chuỗi hạt chung
Với hai chuỗi hạt như bài trước, lần này Gấu Po muốn xem tận mắt chuỗi hạt chung dài nhất. Hãy in ra một chuỗi như vậy.
| Đầu vào | Dòng 1: xâu a. Dòng 2: xâu b. Mỗi xâu gồm từ 1 đến 1000 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một xâu là chuỗi hạt chung dài nhất. Nếu có nhiều đáp án, in đáp án nào cũng được. Nếu không có hạt nào chung, in một dòng trống. | |
| Test | Input | Output |
| 1 | abcde ace | ace |
| 2 | aggtab gxtxayb | gtab |
Bài 3. Sửa tin nhắn
Thỏ gõ nhầm tin nhắn thành xâu a nhưng muốn gửi xâu b. Mỗi lần, Thỏ được xóa một ký tự bất kỳ của xâu hiện tại, hoặc chèn một ký tự bất kỳ vào vị trí bất kỳ. Hỏi Thỏ cần ít nhất bao nhiêu thao tác để biến a thành b?
| Đầu vào | Dòng 1: xâu a. Dòng 2: xâu b. Mỗi xâu gồm từ 1 đến 2000 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một số nguyên là số thao tác ít nhất. | |
| Test | Input | Output |
| 1 | abcde ace | 2 |
| 2 | hello help | 3 |
Bài 4. Gấu Po đi lấy mật
Gấu Po đứng ở ô (1, 1) của khu rừng có dạng lưới n × m ô và muốn đến ô (n, m) có tổ ong. Mỗi bước, Gấu Po chỉ được sang ô bên phải hoặc ô bên dưới. Hỏi có bao nhiêu đường đi khác nhau?
| Đầu vào | Một dòng gồm hai số nguyên n, m (1 ≤ n, m ≤ 30). | |
|---|---|---|
| Đầu ra | Một số nguyên là số đường đi (hãy dùng long long). | |
| Test | Input | Output |
| 1 | 3 3 | 6 |
| 2 | 1 5 | 1 |
| 3 | 30 30 | 30067266499541040 |
Bài 5. Rừng có cây chắn
Khu rừng của Gấu Po bây giờ có một số cây to chắn lối. Lưới gồm n dòng, mỗi dòng m ký tự: ô '.' là lối đi, ô '#' là cây to (không đi qua được). Gấu Po đi từ ô (1, 1) đến ô (n, m), mỗi bước sang phải hoặc xuống dưới. Hỏi có bao nhiêu đường đi?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 30). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Một số nguyên là số đường đi. In 0 nếu không có đường nào (kể cả khi ô xuất phát hoặc ô đích là cây). | |
| Test | Input | Output |
| 1 | 3 3 ... .#. ... | 2 |
| 2 | 3 3 .#. .#. ... | 1 |
| 3 | 2 2 .# #. | 0 |
Bài 6. Nhặt hạt dẻ
Thỏ đi từ ô (1, 1) đến ô (n, m) của lưới n × m, mỗi bước sang phải hoặc xuống dưới. Ô (i, j) có a[i][j] hạt dẻ và Thỏ nhặt hết hạt dẻ ở mọi ô đi qua (kể cả ô đầu và ô cuối). Thỏ nhặt được nhiều nhất bao nhiêu hạt?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo, mỗi dòng m số nguyên a[i][j] (0 ≤ a[i][j] ≤ 100). | |
|---|---|---|
| Đầu ra | Một số nguyên là số hạt dẻ nhiều nhất. | |
| Test | Input | Output |
| 1 | 3 3 1 3 1 1 5 1 4 2 1 | 12 |
| 2 | 2 4 0 2 0 9 7 0 1 1 | 12 |
Bài 7. Đường đi nhẹ nhàng nhất
Hổ chạy từ ô (1, 1) đến ô (n, m) của một sân tập n × m, mỗi bước sang phải hoặc xuống dưới. Ô (i, j) làm Hổ mất a[i][j] sức khi đi qua (kể cả ô đầu và ô cuối). Hãy tìm tổng sức mất ít nhất và in ra một đường đi tốt nhất.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo, mỗi dòng m số nguyên a[i][j] (1 ≤ a[i][j] ≤ 100). | |
|---|---|---|
| Đầu ra | Dòng 1: tổng sức mất ít nhất. Dòng 2: xâu gồm n + m - 2 ký tự, mỗi ký tự là 'R' (sang phải) hoặc 'D' (xuống dưới). Nếu có nhiều đường đi tốt nhất, in đường nào cũng được. | |
| Test | Input | Output |
| 1 | 3 3 1 3 1 1 5 1 4 2 1 | 7 RRDD |
| 2 | 3 4 2 1 9 9 9 3 1 9 9 9 2 1 | 10 RDRDR |
Bài 8. Tháp kẹo hình tam giác
Hổ xếp kẹo thành một tháp tam giác có n tầng, tầng thứ i có i ô, ô thứ j của tầng i chứa a[i][j] viên kẹo. Thỏ xuất phát ở ô duy nhất của tầng 1, mỗi bước đi xuống tầng dưới, vào ô ngay bên dưới (cùng vị trí j) hoặc ô bên dưới lệch sang phải (vị trí j + 1). Thỏ nhặt hết kẹo ở mọi ô đi qua. Hỏi Thỏ nhặt được nhiều nhất bao nhiêu viên kẹo khi xuống đến tầng n?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). n dòng tiếp theo, dòng thứ i gồm i số nguyên a[i][j] (0 ≤ a[i][j] ≤ 100). | |
|---|---|---|
| Đầu ra | Một số nguyên là số kẹo nhiều nhất. | |
| Test | Input | Output |
| 1 | 4 3 7 4 2 4 6 8 5 9 3 | 23 |
| 2 | 3 5 1 1 9 1 1 | 15 |
Bài 9. Ghé qua kho báu
Gấu Po đi từ ô (1, 1) đến ô (n, m) của lưới n × m, mỗi bước sang phải hoặc xuống dưới. Lần này có một kho báu ở ô (x, y) và Gấu Po nhất định phải đi qua ô đó. Hỏi có bao nhiêu đường đi?
| Đầu vào | Một dòng gồm bốn số nguyên n, m, x, y (1 ≤ x ≤ n ≤ 30; 1 ≤ y ≤ m ≤ 30). | |
|---|---|---|
| Đầu ra | Một số nguyên là số đường đi. | |
| Test | Input | Output |
| 1 | 3 3 2 2 | 4 |
| 2 | 4 5 2 3 | 18 |
Bài tập tự luyện
Bài 1. Hai dãy điểm danh
Thỏ và Hổ mỗi người ghi lại các số báo danh theo thứ tự các bạn bước vào lớp trong hai ngày. Dãy của Thỏ có n số, dãy của Hổ có m số. Hai bạn muốn biết dãy con chung dài nhất của hai dãy có độ dài bao nhiêu.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 2000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). Dòng 3: m số nguyên b[j] (1 ≤ b[j] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên là độ dài dãy con chung dài nhất. | |
| Test | Input | Output |
| 1 | 5 6 1 3 5 7 9 3 1 5 9 7 9 | 4 |
| 2 | 4 3 2 2 2 2 1 2 1 | 1 |
Bài 2. Chuỗi hạt đối xứng
Gấu Po có chuỗi hạt s. Gấu Po muốn bỏ bớt một vài hạt (không đổi thứ tự các hạt còn lại) để được chuỗi đối xứng, tức là đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Chuỗi đối xứng dài nhất có bao nhiêu hạt?
| Đầu vào | Một dòng duy nhất là xâu s gồm từ 1 đến 2000 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một số nguyên là độ dài lớn nhất. | |
| Test | Input | Output |
| 1 | bbabcbcab | 7 |
| 2 | abcd | 1 |
Bài 3. Làm đẹp tên
Thỏ có một cái tên là xâu s. Thỏ muốn chèn thêm các ký tự vào vị trí bất kỳ (không xóa, không đổi chỗ ký tự cũ) để tên đọc xuôi hay ngược đều giống nhau. Thỏ cần chèn ít nhất bao nhiêu ký tự?
| Đầu vào | Một dòng duy nhất là xâu s gồm từ 1 đến 2000 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một số nguyên là số ký tự cần chèn ít nhất. | |
| Test | Input | Output |
| 1 | abcd | 3 |
| 2 | aab | 1 |
| 3 | racecar | 0 |
Bài 4. Lối đi trong rừng hạt dẻ
Lưới n × m của Hổ có hai loại ô: ô '#' là cây to không đi qua được, ô là chữ số từ '0' đến '9' cho biết số hạt dẻ ở ô đó. Hổ đi từ ô (1, 1) đến ô (n, m), mỗi bước sang phải hoặc xuống dưới, không đi qua cây, và nhặt hết hạt dẻ ở mọi ô đi qua. Hỏi Hổ nhặt được nhiều nhất bao nhiêu hạt? Nếu không có đường đến ô (n, m), in -1.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo, mỗi dòng gồm m ký tự là '#' hoặc chữ số từ '0' đến '9'. | |
|---|---|---|
| Đầu ra | Một số nguyên là số hạt dẻ nhiều nhất, hoặc -1 nếu không có đường đi. | |
| Test | Input | Output |
| 1 | 3 4 1#23 4562 #781 | 26 |
| 2 | 2 3 1#3 #25 | -1 |
Bài 5. Thả bi
Gấu Po có một bảng n hàng, m cột, ô (i, j) có a[i][j] điểm. Gấu Po thả một viên bi vào một ô bất kỳ của hàng 1. Mỗi bước, viên bi rơi xuống hàng kế tiếp, vào ô ngay bên dưới, hoặc ô chéo bên trái, hoặc ô chéo bên phải (nếu ô đó còn nằm trong bảng). Viên bi ăn điểm của mọi ô đi qua, đến hàng n thì dừng. Tổng điểm lớn nhất có thể đạt được là bao nhiêu?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo, mỗi dòng m số nguyên a[i][j] (0 ≤ a[i][j] ≤ 100). | |
|---|---|---|
| Đầu ra | Một số nguyên là tổng điểm lớn nhất. | |
| Test | Input | Output |
| 1 | 3 3 1 2 3 9 1 1 1 1 5 | 12 |
| 2 | 4 1 3 1 4 1 | 9 |
Bài 6. Bao nhiêu cách nhặt nhiều nhất
Cho lưới n × m, ô (i, j) có a[i][j] hạt dẻ. Thỏ đi từ ô (1, 1) đến ô (n, m), mỗi bước sang phải hoặc xuống dưới và nhặt hết hạt dẻ ở mọi ô đi qua. Hãy cho biết số hạt dẻ nhiều nhất Thỏ nhặt được và có bao nhiêu đường đi khác nhau nhặt được đúng số hạt nhiều nhất đó.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 30). n dòng tiếp theo, mỗi dòng m số nguyên a[i][j] (0 ≤ a[i][j] ≤ 9). | |
|---|---|---|
| Đầu ra | Một dòng gồm hai số nguyên cách nhau một dấu cách: số hạt dẻ nhiều nhất và số đường đi đạt được số hạt đó. | |
| Test | Input | Output |
| 1 | 3 3 1 3 1 1 5 1 4 2 1 | 12 1 |
| 2 | 2 3 1 1 1 1 1 1 | 4 3 |
Bài 7. Mảnh vườn vuông
Mảnh vườn của Hổ là lưới n × m, ô '1' là đất tốt, ô '0' là đất xấu. Hổ muốn chọn một mảnh vườn hình vuông gồm toàn ô đất tốt (các ô liền nhau, hai cạnh song song với mép lưới). Cạnh dài nhất của một hình vuông như vậy là bao nhiêu?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo, mỗi dòng gồm m ký tự '0' hoặc '1'. | |
|---|---|---|
| Đầu ra | Một số nguyên là độ dài cạnh lớn nhất (in 0 nếu không có ô đất tốt nào). | |
| Test | Input | Output |
| 1 | 4 5 10110 10111 11111 10010 | 2 |
| 2 | 2 2 00 00 | 0 |
Bài 8. Ba bạn cùng nhớ
Gấu Po, Thỏ và Hổ mỗi người nhớ một xâu ký tự. Họ muốn tìm xâu dài nhất là dãy con của cả ba xâu. Hãy tính độ dài của xâu đó.
| Đầu vào | Ba dòng, mỗi dòng là một xâu gồm từ 1 đến 100 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một số nguyên là độ dài dãy con chung dài nhất của ba xâu. | |
| Test | Input | Output |
| 1 | abcde aebdc abdce | 3 |
| 2 | abc def ghi | 0 |
Bài 9. Thử thách (không bắt buộc): Sửa đúng từ
Thỏ muốn biến từ a thành từ b. Mỗi bước, Thỏ được chọn một trong ba thao tác: chèn một ký tự vào vị trí bất kỳ, xóa một ký tự bất kỳ, hoặc đổi một ký tự thành ký tự khác. Hỏi Thỏ cần ít nhất bao nhiêu bước?
| Đầu vào | Dòng 1: xâu a. Dòng 2: xâu b. Mỗi xâu gồm từ 1 đến 1000 chữ cái thường. | |
|---|---|---|
| Đầu ra | Một số nguyên là số bước ít nhất. | |
| Test | Input | Output |
| 1 | kitten sitting | 3 |
| 2 | sunday saturday | 3 |
-
Gợi ý chung: Với hai xâu, hãy để dp có kích thước (n + 1) × (m + 1) và nhớ rằng dp[i][j] nói về i ký tự đầu, nên ký tự cuối tương ứng là a[i - 1], b[j - 1]; viết a[i] hay b[j] là lỗi hay gặp nhất. Với lưới, bài đếm đường đi dùng long long và đặt hàng 0, cột 0 bằng 0; bài tổng nhỏ nhất thì hàng 0, cột 0 phải là INF (trừ dp[0][1] = 0). Khi có ô tường, hãy nghĩ xem ô đó có thể “nhận” đường từ ô trước hay không, và kiểm tra riêng trường hợp ô xuất phát là tường. Nhiều bài có thể đưa về LCS: số thao tác xóa/chèn là n + m - 2 × LCS, xâu đối xứng dài nhất là LCS của xâu với xâu đảo ngược của nó.
-
Lưu ý thêm: Trước khi viết code, em hãy làm đủ bốn việc: (1) nói được dp[i][j] nghĩa là gì, (2) viết công thức cho ô thường, (3) viết giá trị các ô cơ sở, (4) chạy tay trên bảng nhỏ của đề mẫu để so với đáp án. Bài Thả bi và Hình vuông lớn nhất có cùng cách nghĩ với đường đi trên lưới: ô hiện tại được tính từ các ô đã tính xong ở hàng trên hoặc bên trái. Bài Sửa đúng từ cũng là bảng dp[i][j] giống LCS nhưng khi hai ký tự cuối khác nhau, em có ba lựa chọn (xóa, chèn, đổi), hãy tự tìm công thức từ ba ô dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1].