Hướng dẫn giải của [2627 KS3] Câu 4: Giao hàng tiết kiệm
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Bài tìm đường đi từ (1, 1) đến (n, m), chỉ đi sang phải hoặc xuống dưới, sao cho tổng giá trị các ô trên đường là lớn nhất. Có K phiếu, mỗi phiếu dùng cho một ô âm trên đường để coi như ô đó bằng 0. Mỗi ô dùng tối đa một phiếu.
Sub 1: Vét cạn trên mọi đường đi — ~O(\binom{n+m-2}{n-1} \cdot (n+m) \log(n+m))~, dùng khi ~n, m \le 10~ và ~K \le 5~
Duyệt mọi đường đi bằng đệ quy. Với mỗi đường, các ô âm nên được đổi bằng phiếu là những ô có giá trị âm nhỏ nhất (|a| lớn nhất). Sắp xếp các ô âm trên đường, lấy tối đa K ô đầu rồi cộng lại giá trị của chúng vào tổng. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Quy hoạch động — ~O(n \cdot m \cdot K)~
Gọi dp[i][j][u] là tổng lớn nhất khi đến ô (i, j) và đã dùng đúng u phiếu. Với ô (i, j), trước hết lấy max của hai ô đứng trước là ô trên và ô bên trái, theo cùng số phiếu u. Nếu ô có giá trị dương hoặc bằng 0 thì cộng giá trị vào. Nếu ô âm thì có hai lựa chọn: trả giá (cộng a, giữ u) hoặc dùng phiếu (không cộng gì, tăng u thêm 1). Ô xuất phát (1, 1) có sẵn 0 phiếu với tổng 0. Đáp án là max của dp[n][m][u] với u \le K. Dùng phiếu không bắt buộc nên lấy max trên mọi u. Bẫy: tổng có thể âm, nên dùng giá trị "không đạt được" đủ âm và kiểm tra trước khi cộng. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc t chuyến. Với mỗi chuyến, nếu n, m \le 10 và K \le 5 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN / 4; // gia tri "khong dat duoc"
int n, m, K;
vector<vector<long long>> g; // g[1..n][1..m]
// Sub 1: vet can. Duyet moi duong tu (1,1) den (n,m) (chi sang phai hoac xuong duoi).
// Voi duong do, cac o am co gia tri nho nhat (am nhat) duoc go bang phieu: chon min(K, so o am) o am
// co |a| lon nhat. Dung khi n, m <= 10, K <= 5
long long best1;
vector<long long> cur; // gia tri cac o tren duong dang xet
void dfs1(int i, int j) {
cur.push_back(g[i][j]);
if (i == n && j == m) {
long long total = 0;
vector<long long> negs;
for (long long v : cur) {
total += v;
if (v < 0) negs.push_back(v);
}
sort(negs.begin(), negs.end()); // am nhat truoc
int take = min<int>(K, negs.size());
for (int t = 0; t < take; t++) total -= negs[t]; // go o am bang phieu: cong lai |v|
best1 = max(best1, total);
} else {
if (i < n) dfs1(i + 1, j);
if (j < m) dfs1(i, j + 1);
}
cur.pop_back();
}
void sub1() {
best1 = LLONG_MIN;
cur.clear();
dfs1(1, 1);
cout << best1 << "\n";
}
// Sub 2 (day du): quy hoach dong. dp[i][j][u] = tong lon nhat den o (i,j) khi da dung dung u phieu.
// Gia tri o am co the tra tien (u giu nguyen, cong a) hoac dung phieu (u+1, cong 0).
// Dap an: max cua dp[n][m][u] voi u <= K. O(n m K)
void sub2() {
int U = K + 1;
vector<long long> dp((size_t)(n + 1) * (m + 1) * U, NEG);
auto idx = [&](int i, int j, int u) { return ((size_t)i * (m + 1) + j) * U + u; };
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
// pre[u] = gia tri tot nhat truoc khi xet o (i,j), voi u phieu da dung
vector<long long> pre(U, NEG);
if (i == 1 && j == 1) pre[0] = 0;
if (i > 1) for (int u = 0; u < U; u++) pre[u] = max(pre[u], dp[idx(i - 1, j, u)]);
if (j > 1) for (int u = 0; u < U; u++) pre[u] = max(pre[u], dp[idx(i, j - 1, u)]);
long long v = g[i][j];
for (int u = 0; u < U; u++) {
long long best = NEG;
if (pre[u] > NEG) best = max(best, pre[u] + v); // khong dung phieu
if (v < 0 && u >= 1 && pre[u - 1] > NEG)
best = max(best, pre[u - 1]); // dung phieu cho o am nay
dp[idx(i, j, u)] = best;
}
}
long long ans = NEG;
for (int u = 0; u < U; u++) ans = max(ans, dp[idx(n, m, u)]);
cout << ans << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> n >> m >> K;
g.assign(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> g[i][j];
if (n <= 10 && m <= 10 && K <= 5) sub1();
else sub2();
}
return 0;
}
Bình luận