Hái sen (Đề tự luyện HSG Tin 9 – Bài 3)
Đề bài
Hái sen. Đầm sen là lưới $N \times M$, ô $(i, j)$ có $a_{i,j}$ bông sen. Xuồng đi từ ô $(1,1)$ tới ô $(N,M)$, mỗi bước sang phải (P) hoặc xuống dưới (X), hái hết sen ở mọi ô đi qua. Mỗi lần đổi hướng (bước sau khác loại bước trước) rất vất vả nên chỉ được đổi hướng tối đa $K$ lần. Tìm tổng sen lớn nhất và đường đi (xâu P/X) đạt được; nếu nhiều đường cùng tốt nhất thì in xâu nhỏ nhất theo thứ tự từ điển. Không có đường hợp lệ thì in $-1$.
Dữ liệu vào: dòng 1 gồm $N, M, K$ $(1 \le N, M \le 200;\ N + M \ge 3;\ 0 \le K \le 20)$; $N$ dòng sau là lưới $(0 \le a_{i,j} \le 10^9)$.
Kết quả: dòng 1 là tổng lớn nhất, dòng 2 là xâu đường đi; hoặc một dòng $-1$.
- Subtask 1 (20%): $N, M \le 8$.
- Subtask 2 (30%): $K \le 2$.
- Subtask 3 (50%): không ràng buộc thêm.
4 5 2
0 0 3 1 6
5 9 7 1 0
0 4 9 5 5
7 4 4 5 836
PPXXXPPĐường PPXXXPP hái $0+0+3+7+9+4+5+8 = 36$ bông, đổi hướng $2$ lần. Đường XXPPPPX cũng được $36$ nhưng xâu lớn hơn. Đường XPPXXPP được $47$ bông nhưng phải đổi hướng $3$ lần.
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 Hái senLời mở đầu
Nếu không có giới hạn đổi hướng, đây là bài "đường đi tổng lớn nhất trên lưới" kinh điển: $f[i][j] = a[i][j] + \max(f[i-1][j], f[i][j-1])$. Giới hạn $K$ làm công thức đó hỏng, vì khi đứng ở ô $(i, j)$ ta chưa biết bước tiếp theo có phải là một lần đổi hướng hay không — điều đó phụ thuộc bước vừa đi vào ô. Vì vậy trạng thái phải nhớ thêm hai thứ:
- hướng $d$ của bước vừa đi vào ô $(i, j)$ (
PhayX); - số lần còn được đổi hướng $r$.
Hình 1. Cùng một ô nhưng đi vào bằng P hay bằng X thì "giá" của bước tiếp theo khác nhau — nên hướng phải nằm trong trạng thái.
Phần thứ hai của bài là truy vết theo thứ tự từ điển: trong các đường tốt nhất phải in xâu nhỏ nhất. Xâu nhỏ nhất được quyết định từ ký tự đầu tiên, nên ta muốn đứng ở ô xuất phát mà biết ngay "nếu đi P thì phần còn lại tốt nhất được bao nhiêu". Đó là lý do lời giải chuẩn tính QHĐ ngược từ ô đích về.
Cách 1Vét cạn mọi đường đi – O(C(N+M−2, N−1) · (N+M)) · 20%
Mỗi đường đi là một xâu gồm $M-1$ chữ P và $N-1$ chữ X. Ta đệ quy sinh mọi xâu như vậy, thử P trước rồi mới tới X, nên các xâu được sinh ra đúng theo thứ tự từ điển. Với mỗi xâu: đếm số lần đổi hướng, nếu không quá $K$ thì tính tổng sen. Chỉ cập nhật đáp án khi tổng lớn hơn hẳn — như vậy trong các đường cùng tổng, đường được giữ lại là đường sinh ra sớm nhất, tức xâu nhỏ nhất.
Với $N = M = 8$ có $\binom{14}{7} = 3432$ đường, quá nhẹ. Nhưng với $N = M = 200$ số đường lớn khủng khiếp ($\binom{398}{199} \approx 10^{118}$).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, K;
vector<vector<ll>> a;
ll best = -1;
string cur, bestPath;
// liet ke MOI duong di: o moi buoc thu 'P' truoc roi 'X'
// -> cac duong di duoc liet ke theo dung thu tu tu dien
void duyet(int i, int j) {
if (i == n - 1 && j == m - 1) {
int t = 0; // dem so lan re cua duong vua tao
for (size_t k = 1; k < cur.size(); k++) t += cur[k] != cur[k - 1];
if (t > K) return;
ll s = a[0][0];
int x = 0, y = 0;
for (char c : cur) { if (c == 'P') y++; else x++; s += a[x][y]; }
if (s > best) { best = s; bestPath = cur; } // chi doi khi LON HON han: giu duong nho nhat
return;
}
if (j + 1 < m) { cur += 'P'; duyet(i, j + 1); cur.pop_back(); }
if (i + 1 < n) { cur += 'X'; duyet(i + 1, j); cur.pop_back(); }
}
int main() {
cin >> n >> m >> K;
a.assign(n, vector<ll>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
duyet(0, 0);
if (best < 0) cout << -1 << '\n';
else cout << best << '\n' << bestPath << '\n';
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m, K = int(data[0]), int(data[1]), int(data[2])
a = [[int(x) for x in data[3 + i * m:3 + (i + 1) * m]] for i in range(n)]
best = [-1, '']
cur = []
# liet ke MOI duong di: o moi buoc thu 'P' truoc roi 'X'
# -> cac duong di duoc liet ke theo dung thu tu tu dien
def duyet(i, j):
if i == n - 1 and j == m - 1:
t = 0 # dem so lan re cua duong vua tao
for k in range(1, len(cur)):
if cur[k] != cur[k - 1]:
t += 1
if t > K:
return
s = a[0][0]; x = y = 0
for c in cur:
if c == 'P': y += 1
else: x += 1
s += a[x][y]
if s > best[0]: # chi doi khi LON HON han: giu duong nho nhat
best[0] = s; best[1] = ''.join(cur)
return
if j + 1 < m:
cur.append('P'); duyet(i, j + 1); cur.pop()
if i + 1 < n:
cur.append('X'); duyet(i + 1, j); cur.pop()
duyet(0, 0)
if best[0] < 0:
print(-1)
else:
print(best[0]); print(best[1])
main()Cách 2Quay lui, cắt nhánh khi vượt K lần rẽ – nhanh khi K ≤ 2 · 50%
Cải tiến Cách 1: trong lúc đệ quy, nhớ số lần đã đổi hướng $t$; bước nào làm $t > K$ thì không đi tiếp nhánh đó. Khi $K \le 2$, số đường hợp lệ rất ít:
- $0$ lần rẽ: chỉ khi $N = 1$ hoặc $M = 1$;
- $1$ lần rẽ:
P…PX…XvàX…XP…P; - $2$ lần rẽ:
P…P X…X P…P(toàn bộ $N-1$ bướcXnằm liền một khúc, chỉ chọn chỗ bắt đầu) hoặcX…X P…P X…X.
Tổng cộng chỉ khoảng $N + M$ đường, mỗi đường dài $N + M - 2$, nên quay lui chạy tức thì với $N, M = 200$. Nhưng khi $K$ lớn (ví dụ $K = 6$), số đường có không quá $K$ lần rẽ lại tăng vọt (cỡ $N^3 M^3$ trở lên) — vẫn quá chậm.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, K;
vector<vector<ll>> a;
ll best = -1;
string cur, bestPath;
// dang o (i, j), da hai duoc tong s, da re t lan; thu 'P' truoc roi 'X'
// -> cac duong di duoc liet ke theo dung thu tu tu dien
void duyet(int i, int j, ll s, int t) {
if (i == n - 1 && j == m - 1) {
if (s > best) { best = s; bestPath = cur; } // chi doi khi LON HON han: giu duong nho nhat
return;
}
char cuoi = cur.empty() ? 0 : cur.back();
if (j + 1 < m) {
int t2 = t + (cuoi == 'X'); // dang di xuong ma re sang phai
if (t2 <= K) { cur += 'P'; duyet(i, j + 1, s + a[i][j + 1], t2); cur.pop_back(); }
}
if (i + 1 < n) {
int t2 = t + (cuoi == 'P'); // dang sang phai ma re xuong
if (t2 <= K) { cur += 'X'; duyet(i + 1, j, s + a[i + 1][j], t2); cur.pop_back(); }
}
}
int main() {
cin >> n >> m >> K;
a.assign(n, vector<ll>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
duyet(0, 0, a[0][0], 0);
if (best < 0) cout << -1 << '\n';
else cout << best << '\n' << bestPath << '\n';
return 0;
}import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.read().split()
n, m, K = int(data[0]), int(data[1]), int(data[2])
a = [[int(x) for x in data[3 + i * m:3 + (i + 1) * m]] for i in range(n)]
best = [-1, '']
cur = []
# dang o (i, j), da hai duoc tong s, da re t lan; thu 'P' truoc roi 'X'
# -> cac duong di duoc liet ke theo dung thu tu tu dien
def duyet(i, j, s, t):
if i == n - 1 and j == m - 1:
if s > best[0]: # chi doi khi LON HON han: giu duong nho nhat
best[0] = s; best[1] = ''.join(cur)
return
cuoi = cur[-1] if cur else ''
if j + 1 < m:
t2 = t + (cuoi == 'X') # dang di xuong ma re sang phai
if t2 <= K:
cur.append('P'); duyet(i, j + 1, s + a[i][j + 1], t2); cur.pop()
if i + 1 < n:
t2 = t + (cuoi == 'P') # dang sang phai ma re xuong
if t2 <= K:
cur.append('X'); duyet(i + 1, j, s + a[i + 1][j], t2); cur.pop()
duyet(0, 0, a[0][0], 0)
if best[0] < 0:
print(-1)
else:
print(best[0]); print(best[1])
main()Cách 3QHĐ ngược trên trạng thái (ô, hướng, số lần rẽ còn lại) – O(N·M·K) · 100%
Gọi $h[i][j][d][r]$ = tổng sen lớn nhất hái được từ ô $(i, j)$ (tính cả ô này) tới ô đích, biết bước vừa đi vào $(i,j)$ có hướng $d$ và còn được đổi hướng tối đa $r$ lần. Ở ô đích $h = a[N][M]$. Ngược lại, ta thử bước tiếp theo:
$$h[i][j][d][r] = a[i][j] + \max\Big(\underbrace{h[i][j+1][P][\,r - [d \ne P]\,]}_{\text{đi }P},\ \underbrace{h[i+1][j][X][\,r - [d \ne X]\,]}_{\text{đi }X}\Big),$$trong đó $[d \ne P]$ bằng $1$ nếu đổi hướng (tốn một lần rẽ), và chỉ xét lựa chọn còn trong lưới và có $r - [\dots] \ge 0$. Không lựa chọn nào hợp lệ thì trạng thái là "không thể". Duyệt $i$ từ dưới lên, $j$ từ phải sang trái thì mọi ô bên phải / bên dưới đã tính xong.
Bước đầu tiên không tính là đổi hướng, nên tổng tốt nhất là $a[1][1] + \max(h[1][2][P][K],\ h[2][1][X][K])$. Cả hai đều "không thể" (chỉ xảy ra khi $K = 0$ và $N, M \ge 2$) thì in $-1$.
Truy vết từ điển nhỏ nhất: đi xuôi từ ô xuất phát, giữ biến need = tổng còn phải hái từ ô đang đứng. Ở mỗi ô, ưu tiên P: nếu đi P hợp lệ và $h$ của ô bên phải (với trạng thái mới) đúng bằng need trừ $a$ ô hiện tại thì đi P; ngược lại bắt buộc đi X. Vì mỗi lần ta chọn ký tự nhỏ nhất có thể mà vẫn đạt tối ưu, xâu thu được là nhỏ nhất.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = LLONG_MIN / 4; // trang thai khong the
int n, m, K;
vector<vector<ll>> a;
// h[i][j][d][r]: tong sen lon nhat hai duoc tu o (i, j) (tinh ca o nay) toi o cuoi,
// biet buoc vua di vao (i, j) theo huong d (0 = P: sang phai, 1 = X: xuong) va con duoc re toi da r lan
static ll h[200][200][2][21];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> K;
a.assign(n, vector<ll>(m));
for (auto &row : a)
for (auto &x : row) cin >> x;
for (int i = n - 1; i >= 0; i--)
for (int j = m - 1; j >= 0; j--)
for (int d = 0; d < 2; d++)
for (int r = 0; r <= K; r++) {
if (i == n - 1 && j == m - 1) { h[i][j][d][r] = a[i][j]; continue; }
ll best = NEG;
// di tiep sang phai: neu huong cu la X thi ton 1 lan re
if (j + 1 < m) {
int r2 = r - (d != 0);
if (r2 >= 0) best = max(best, h[i][j + 1][0][r2]);
}
// di tiep xuong duoi: neu huong cu la P thi ton 1 lan re
if (i + 1 < n) {
int r2 = r - (d != 1);
if (r2 >= 0) best = max(best, h[i + 1][j][1][r2]);
}
h[i][j][d][r] = (best == NEG) ? NEG : best + a[i][j];
}
// buoc dau tien khong tinh la re
ll vP = (m > 1) ? h[0][1][0][K] : NEG;
ll vX = (n > 1) ? h[1][0][1][K] : NEG;
ll ans = max(vP, vX);
if (ans < 0) { cout << -1 << '\n'; return 0; }
cout << ans + a[0][0] << '\n';
// dung lai duong di: moi buoc uu tien 'P' (nho hon 'X') neu van dat toi uu
string path;
int i = 0, j = 0, d, r = K;
if (vP == ans) { d = 0; j = 1; path += 'P'; }
else { d = 1; i = 1; path += 'X'; }
ll need = ans; // tong can dat tu o (i, j) tro di
while (i != n - 1 || j != m - 1) {
need -= a[i][j];
if (j + 1 < m && r - (d != 0) >= 0 && h[i][j + 1][0][r - (d != 0)] == need) {
r -= (d != 0); d = 0; j++; path += 'P';
} else {
r -= (d != 1); d = 1; i++; path += 'X';
}
}
cout << path << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, K = int(data[0]), int(data[1]), int(data[2])
a = [[int(x) for x in data[3 + i * m:3 + (i + 1) * m]] for i in range(n)]
NEG = -(1 << 62) # trang thai khong the
R = range(K + 1)
dead = [NEG] * (K + 1)
# HP[i][j][r] / HX[i][j][r]: tong sen lon nhat tu o (i, j) (tinh ca o nay) toi o cuoi,
# biet buoc vua di vao (i, j) la P (sang phai) / X (xuong) va con duoc re toi da r lan
HP = [[None] * m for _ in range(n)]
HX = [[None] * m for _ in range(n)]
for i in range(n - 1, -1, -1):
rowP = HP[i]; rowX = HX[i]; ai = a[i]
for j in range(m - 1, -1, -1):
v = ai[j]
if i == n - 1 and j == m - 1:
rowP[j] = [v] * (K + 1); rowX[j] = [v] * (K + 1)
continue
nP = rowP[j + 1] if j + 1 < m else dead # di tiep sang phai, huong vao o moi la P
nX = HX[i + 1][j] if i + 1 < n else dead # di tiep xuong, huong vao o moi la X
sX = [NEG] + nX[:K] # re (P -> X) ton 1 lan: dung r - 1
sP = [NEG] + nP[:K] # re (X -> P) ton 1 lan
rowP[j] = [(p if p > x else x) + v for p, x in zip(nP, sX)] # huong cu P
rowX[j] = [(p if p > x else x) + v for p, x in zip(sP, nX)] # huong cu X
vP = HP[0][1][K] if m > 1 else NEG
vX = HX[1][0][K] if n > 1 else NEG
ans = max(vP, vX)
if ans < 0:
print(-1)
return
out = [str(ans + a[0][0])]
# dung lai duong di: moi buoc uu tien 'P' (nho hon 'X') neu van dat toi uu
path = []
r = K
if vP == ans:
d, i, j = 0, 0, 1; path.append('P')
else:
d, i, j = 1, 1, 0; path.append('X')
need = ans
while i != n - 1 or j != m - 1:
need -= a[i][j]
r2 = r - (d != 0)
if j + 1 < m and r2 >= 0 and HP[i][j + 1][r2] == need:
r = r2; d = 0; j += 1; path.append('P')
else:
r -= (d != 1); d = 1; i += 1; path.append('X')
out.append(''.join(path))
print('\n'.join(out))
main()long long.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 34 test: Subtask 1 có 12 test ($N, M \le 8$; gồm ví dụ, lưới $1 \times 2$ với $K = 0$, lưới $2 \times 2$ với $K = 0$ (đáp án $-1$), lưới toàn $0$), Subtask 2 có 10 test ($K \le 2$, $N, M$ từ $150$ tới $200$), Subtask 3 có 12 test ($N, M \approx 200$, $K$ từ $6$ tới $20$). Các kiểu lưới: số lớn tới $10^9$ (tổng tràn int), số nhỏ $0..3$ (rất nhiều đường bằng nhau), chỉ hai giá trị lớn (vừa nhiều đường bằng nhau vừa tràn int), "bậc thang" sen muốn hái hết phải rẽ rất nhiều lần. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (12 test) | Sub 2 (10 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Vét cạn mọi đường | Đúng 12/12 | TLE 0/10 | TLE 0/12 | 20 |
| Cách 2 – Quay lui cắt nhánh | Đúng 12/12 | Đúng 10/10 | TLE 0/12 | 50 |
| Cách 3 – QHĐ (ô, hướng, r) (chuẩn) | Đúng 12/12 | Đúng 10/10 | Đúng 12/12 | 100 |
| Sai: QHĐ xuôi, truy vết ngược (đường không nhỏ nhất) | WA 9/12 | WA 8/10 | WA 5/12 | 59,8 |
Sai: lưu tổng bằng int | WA 7/12 | WA 5/10 | WA 4/12 | 43,3 |
| Sai: đếm cả bước đầu là một lần rẽ | WA 6/12 | WA 2/10 | WA 3/12 | 28,5 |
| Sai: quên giới hạn $K$ (QHĐ kinh điển) | WA 7/12 | WA 1/10 | WA 1/12 | 18,8 |
| Sai: tham lam đi sang ô kề nhiều sen hơn | WA 5/12 | WA 2/10 | WA 1/12 | 18,5 |
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 12/12 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 22 test còn lại; Cách 2 đúng 22/22 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3; Cách 3 đúng 34/34 test, test lâu nhất chạy khoảng 0,02 giây. Lời giải Python của Cách 3 cũng đúng 34/34 test, chạy tối đa khoảng 0,33 giây với CPython. Ví dụ của đề cố tình chọn sao cho lời giải "QHĐ xuôi, truy vết ngược" và lời giải dùng int vẫn in đúng 36 và PPXXXPP — nhớ tự thử thêm test có nhiều đường bằng nhau 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