Vườn sầu riêng (Đề tự luyện HSG Tin 9 – Bài 4) – Quy hoạch động trên lưới kết hợp cái túi: trạng thái (ô, khối lượng)
Đề bài
Vườn sầu riêng. Lưới $N \times M$, ô $(i, j)$ có giá trị $w_{i,j}$: $-1$ là mương nước (không đi vào được), $0$ là cây chưa có trái, $w_{i,j} > 0$ là một trái nặng $w_{i,j}$ kg. Thầy Sơn đi từ $(1, 1)$ đến $(N, M)$, mỗi bước sang phải hoặc xuống dưới; ở mỗi ô đi qua có thể hái hoặc không hái trái. Giỏ chịu tối đa $W$ kg. Tìm tổng khối lượng lớn nhất có thể hái (không vượt $W$), hoặc $-1$ nếu không có đường đi.
Dữ liệu vào: $N, M, W$ $(1 \le N, M \le 100;\ 1 \le W \le 10^4)$; $N$ dòng, mỗi dòng $M$ số $w_{i,j}$ $(-1 \le w_{i,j} \le 10^4)$.
Kết quả: tổng khối lượng lớn nhất, hoặc $-1$.
- Subtask 1 (20%): $N, M \le 5$.
- Subtask 2 (30%): $N, M \le 10$, $W \le 1000$.
- Subtask 3 (50%): không ràng buộc thêm.
3 4 15
7 -1 7 6
7 0 10 12
7 10 9 1114Đi $(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3) \to (3,4)$, hái hai trái $7$ kg ở $(1,1)$ và $(2,1)$: giỏ nặng $14$ kg. Không có cách nào được đúng $15$ kg; ô $(1,3)$, $(1,4)$ không đi tới được vì $(1,2)$ là mương.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Vườn sầu riêngLời mở đầu
Bài này là "con lai" của hai bài quy hoạch động kinh điển: đường đi trên lưới (chỉ sang phải / xuống dưới) và cái túi 0/1 (mỗi món lấy hoặc không, tổng không vượt sức chứa). Cái khó là hai thứ đan vào nhau, và hai lối tắt "trông có vẻ đúng" đều sai:
Hình 1. Giữ "khối lượng lớn nhất" ở mỗi ô (bẫy 1) hay chọn đường trước rồi mới chọn trái (bẫy 2) đều sai.
Cách 1Thử mọi đường đi và mọi cách hái – O(C · 2^L · L) · 20%
Đệ quy di(i, j) đi sang phải hoặc xuống dưới, ghi lại các trái trên đường vào mảng duong. Khi tới đích, thử mọi tập con (bitmask) các trái trên đường và giữ tổng lớn nhất $\le W$. Với $N, M \le 5$: đường dài $L \le 9$ ô, có không quá $\binom{8}{4} = 70$ đường, mỗi đường $2^9 = 512$ tập con — rất nhanh.
#include <bits/stdc++.h>
using namespace std;
int n, m, W, ans = -1;
int a[105][105];
vector<int> duong; // khoi luong cac trai tren duong dang di
void di(int i, int j) {
if (a[i][j] == -1) return; // muong nuoc
duong.push_back(a[i][j]);
if (i == n && j == m) { // toi dich: thu moi cach chon trai de hai
int k = duong.size();
for (int mask = 0; mask < (1 << k); mask++) {
int tong = 0;
for (int b = 0; b < k; b++)
if (mask >> b & 1) tong += duong[b];
if (tong <= W) ans = max(ans, tong);
}
} else {
if (j < m) di(i, j + 1); // sang phai
if (i < n) di(i + 1, j); // xuong duoi
}
duong.pop_back();
}
int main() {
cin >> n >> m >> W;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
di(1, 1);
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m, W = int(data[0]), int(data[1]), int(data[2])
a = [[0] * (m + 1)] + [[0] + [int(data[3 + i * m + j]) for j in range(m)] for i in range(n)]
ans = -1
duong = [] # khoi luong cac trai tren duong dang di
def di(i, j):
nonlocal ans
if a[i][j] == -1:
return # muong nuoc
duong.append(a[i][j])
if i == n and j == m: # toi dich: thu moi cach chon trai de hai
k = len(duong)
for mask in range(1 << k):
tong = 0
for b in range(k):
if mask >> b & 1:
tong += duong[b]
if tong <= W and tong > ans:
ans = tong
else:
if j < m: di(i, j + 1) # sang phai
if i < n: di(i + 1, j) # xuong duoi
duong.pop()
di(1, 1)
print(ans)
main()Cách 2Mọi đường đi, mang theo "cái túi" – O(số đoạn đường · W) · 50%
Thay vì thử $2^L$ tập con ở đích, ta làm cái túi 0/1 ngay trên đường đi: mảng f[s] cho biết có thể hái được đúng $s$ kg từ các trái đã đi qua hay không. Ban đầu chỉ f[0] = 1. Khi đi qua trái nặng $w$:
for (s = W; s >= w; s--) if (f[s - w]) f[s] = 1;
f[s - w] có thể vừa được bật ngay trong vòng này (nhờ chính trái $w$), nên một trái bị "hái" hai, ba lần. Ví dụ trái $3$ kg, duyệt tăng thì bật f[3], rồi từ f[3] bật tiếp f[6], f[9]… — sai! Duyệt giảm thì f[s - w] luôn là giá trị trước khi xét trái này.Hàm đệ quy nhận bản sao của mảng f, nên rẽ phải hay rẽ xuống không ảnh hưởng nhau. Với $N, M \le 10$ có khoảng $1{,}8 \cdot 10^5$ đoạn đường bắt đầu từ $(1,1)$, mỗi đoạn tốn $O(W) = 1000$ phép — ổn.
#include <bits/stdc++.h>
using namespace std;
int n, m, W, ans = -1;
int a[105][105];
// f[s] = 1 neu tren doan duong da di co the hai duoc dung s kg
void di(int i, int j, vector<char> f) {
if (a[i][j] == -1) return; // muong nuoc
int w = a[i][j];
if (w > 0)
for (int s = W; s >= w; s--) // them trai o (i, j) vao cai tui
if (f[s - w]) f[s] = 1;
if (i == n && j == m) { // toi dich: lay khoi luong lon nhat co the
for (int s = W; s >= 0; s--)
if (f[s]) { ans = max(ans, s); break; }
return;
}
if (j < m) di(i, j + 1, f); // sang phai (mang f duoc sao chep)
if (i < n) di(i + 1, j, f); // xuong duoi
}
int main() {
cin >> n >> m >> W;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
vector<char> f(W + 1, 0);
f[0] = 1; // gio rong
di(1, 1, f);
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m, W = int(data[0]), int(data[1]), int(data[2])
a = [[0] * (m + 1)] + [[0] + [int(data[3 + i * m + j]) for j in range(m)] for i in range(n)]
mask = (1 << (W + 1)) - 1
ans = -1
# f: bit thu s bang 1 neu tren doan duong da di co the hai duoc dung s kg
def di(i, j, f):
nonlocal ans
if a[i][j] == -1:
return # muong nuoc
if a[i][j] > 0:
f |= (f << a[i][j]) & mask # them trai o (i, j) vao cai tui
if i == n and j == m: # toi dich: lay khoi luong lon nhat co the
ans = max(ans, f.bit_length() - 1)
return
if j < m: di(i, j + 1, f) # sang phai
if i < n: di(i + 1, j, f) # xuong duoi
di(1, 1, 1) # gio rong: chi co bit 0
print(ans)
main()Nhưng với lưới $100 \times 100$, số đường đi là $\binom{198}{99} \approx 2{,}3 \cdot 10^{58}$ — không bao giờ chạy xong.
Cách 3Quy hoạch động trạng thái (ô, khối lượng) – O(N · M · W) · 100%
Nhận xét then chốt: hai đoạn đường khác nhau cùng tới ô $(i, j)$ với cùng khối lượng giỏ $s$ thì tương lai như nhau — đi tiếp thế nào cũng được kết quả giống nhau. Vậy chỉ cần nhớ tập các khối lượng có thể có tại mỗi ô, không cần nhớ đường đi:
- Ô mương nước: tập rỗng.
- Ô $(1, 1)$: trước khi hái, tập là $\{0\}$.
- Ô khác: tập trước khi hái = (tập của ô trên) $\cup$ (tập của ô bên trái).
- Rồi xử lý trái ở ô này đúng như cái túi 0/1: mỗi $s$ trong tập sinh thêm $s + w$ (nếu $\le W$), duyệt $s$ giảm dần.
Đáp án là phần tử lớn nhất trong tập của ô $(N, M)$; tập rỗng thì in $-1$. Khi cài đặt, ta lưu tập bằng mảng đúng/sai f[j][s] và lăn theo hàng: trước khi cập nhật, f[j] đang là tập của ô phía trên $(i-1, j)$, còn f[j-1] đã là tập của ô bên trái $(i, j-1)$. Bộ nhớ chỉ $M \cdot (W+1) \approx 10^6$ byte.
Mô phỏng: mỗi ô hiện tập các khối lượng có thể có trong giỏ khi rời ô đó.
Code hoàn chỉnh. Bản Python lưu cả tập khối lượng trong một số nguyên: bit thứ $s$ bằng $1$ nghĩa là "giỏ có thể nặng $s$ kg". Hợp hai tập là phép |, còn "hái trái $w$ kg" là cur | (cur << w) (dịch trái $w$ bit = cộng $w$ vào mọi phần tử), rồi & mask để bỏ các tổng vượt $W$. Đáp án là vị trí bit cao nhất: bit_length() - 1.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, W;
cin >> n >> m >> W;
vector<vector<int>> a(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
// f[j][s] = 1 neu di duoc toi o (i, j) cua hang dang xet ma trong gio co dung s kg
vector<vector<char>> f(m + 1, vector<char>(W + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
vector<char> &cur = f[j]; // truoc khi cap nhat: gia tri cua o (i-1, j)
if (a[i][j] == -1) { // muong nuoc: khong di qua duoc
fill(cur.begin(), cur.end(), 0);
continue;
}
if (i == 1 && j == 1) cur[0] = 1; // xuat phat voi gio rong
else if (j > 1)
for (int s = 0; s <= W; s++) cur[s] |= f[j - 1][s]; // den tu o tren hoac o ben trai
int w = a[i][j];
if (w > 0)
for (int s = W; s >= w; s--) // hai trai o (i, j): duyet s GIAM dan
if (cur[s - w]) cur[s] = 1;
}
int ans = -1; // -1: khong co duong di
for (int s = W; s >= 0; s--)
if (f[m][s]) { ans = s; break; }
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); W = int(data[2])
a = list(map(int, data[3:3 + n * m]))
mask = (1 << (W + 1)) - 1
# f[j]: so nguyen ma bit thu s bang 1 neu di duoc toi o (i, j) voi gio nang dung s kg
f = [0] * (m + 1)
k = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
w = a[k]; k += 1
if w == -1:
f[j] = 0 # muong nuoc: khong di qua duoc
continue
if i == 1 and j == 1:
cur = 1 # xuat phat voi gio rong (bit 0)
else:
cur = f[j] | f[j - 1] # den tu o tren hoac o ben trai
if w > 0:
cur |= (cur << w) & mask # hai trai o (i, j): moi khoi luong s sinh them s + w
f[j] = cur
print(f[m].bit_length() - 1) # bit cao nhat; f[m] = 0 thi in -1
main()f[i][j][s] cũng được (khoảng $10^8$ byte = 100 MB, vẫn dưới 256 MB) và dễ hiểu hơn. Cách "lăn theo hàng" ở trên chỉ tiết kiệm bộ nhớ. Một chi tiết hay: với ô ở cột 1, f[1] đang là tập của ô phía trên — đúng thứ ta cần, nên không phải làm gì.14!Bộ test chấm "bắt" những lỗi nào?
Bộ test có 31 test: Subtask 1 có 10 test ($N, M \le 5$: ví dụ, lưới $1 \times 1$ với trái nặng hơn giỏ hoặc vừa khít $W = 10^4$, ô xuất phát là mương, ô đích bị mương chắn, …), Subtask 2 có 9 test (lưới $10 \times 10$ hoặc $9 \times 10$, $W$ từ 700 tới 1000), Subtask 3 có 12 test (lưới gần $100 \times 100$, $W \approx 10^4$). Các kiểu dữ liệu: trái to ($W/8$ tới $W/2$, tham lam dễ hụt), hầu hết trái là bội của một số $B$ trừ vài trái "đặc biệt" (phải đi đúng đường mới hái đủ gần $W$), nhiều mương nước, ít trái nhỏ (tổng mọi trái trên đường nhỏ hơn $W$: lỗi duyệt tăng sẽ "hái lặp" vượt quá), không có đường đi (ở Subtask 1 và 3). Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (9 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Mọi đường × mọi cách hái | Đúng 10/10 | TLE 0/9 | TLE 0/12 | 20 |
| Cách 2 – Mọi đường + cái túi | Đúng 10/10 | Đúng 9/9 | TLE 0/12 | 50 |
| Cách 3 – QHĐ (ô, khối lượng) (chuẩn) | Đúng 10/10 | Đúng 9/9 | Đúng 12/12 | 100 |
| Sai: mỗi ô chỉ nhớ giỏ nặng nhất | WA 7/10 | WA 2/9 | WA 6/12 | 45,7 |
| Sai: chọn đường nhiều trái nhất rồi mới chọn trái | WA 9/10 | WA 6/9 | WA 4/12 | 54,7 |
| Sai: cái túi duyệt s tăng dần | WA 9/10 | WA 6/9 | WA 6/12 | 63,0 |
| Sai: không có đường vẫn in 0 | WA 8/10 | Đúng 9/9 | WA 11/12 | 91,8 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 21 test còn lại; Cách 2 đúng 19/19 test của hai subtask đầu và quá thời gian cả 12 test Subtask 3; Cách 3 đúng 31/31 test, test lâu nhất chạy khoảng 0,17 giây. Lời giải Python của Cách 3 (dùng số nguyên làm "dãy bit") cũng đúng 31/31 test, chạy tối đa khoảng 0,03 giây với CPython. Ví dụ của đề khá "hiền": cách tham lam và cách "chọn đường nhiều trái nhất" tình cờ đều hái được 14 kg, còn các trái đi tới được (7, 9, 10, 11, 12 kg) dù hái lặp cũng không ghép nổi 15 kg — nên cả bốn lời giải sai ở bảng trên đều vẫn ra đúng 14. Nhớ tự nghĩ thêm test nha!
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét