Hướng dẫn giải của Trò chơi Mario (KS3)
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
Mario xuất phát ở ống trụ 1 với năng lượng ~E~, mỗi lần đi từ ~u~ sang ~v~ mất ~C_{uv} = d \cdot (|x_u - x_v| + |y_u - y_v|)~; khi vừa tới một ống khác ~N~ thì năng lượng phải ~\ge 0~ rồi mới được cộng ~A_i~; mỗi ống dùng một lần. Tìm ~E~ nhỏ nhất để tới được ống ~N~ (khi tới ~N~ năng lượng cũng phải ~\ge 0~ — ví dụ cho kết quả ~2~ chứ không phải ~1~).
Sub 1: Quy hoạch động trên tập — ~O(2^n \cdot n^2)~, dùng khi ~n \le 16~
Gọi ~h[mask][u]~ là năng lượng tối thiểu cần có khi vừa tới ~u~ (chưa cộng ~A_u~), biết tập ống đã đi là ~mask~. Ta có ~h[mask][N] = 0~ và
~h[mask][u] = \max(0,\ \min_{v \notin mask} (h[mask \cup \{v\}][v] + C_{uv} - A_u))~.
Duyệt ~mask~ giảm dần, đáp án là ~h[\{1\}][1]~. Đây là cách làm chính xác theo đúng đề (mỗi ống dùng một lần, kiểm tra năng lượng tại từng bước).
Sub 2: Chặt nhị phân năng lượng + tham lam kiểu Dijkstra — ~O(n^2 \log V)~
Chặt nhị phân ~E~ trong đoạn ~[0, C_{1N}]~ (đi thẳng từ 1 tới ~N~ luôn được với ~E = C_{1N}~). Với mỗi ~E~, làm giống Dijkstra: ~best[v]~ là năng lượng lớn nhất khi vừa tới ~v~; mỗi bước chốt ống chưa chốt có ~best~ lớn nhất (và ~\ge 0~), rồi cập nhật ~best[v] = \max(best[v],\ best[u] + A_u - C_{uv})~ nếu giá trị này ~\ge 0~. Nếu chốt được ống ~N~ thì ~E~ đủ.
Cách này luôn tìm ra một đường đi hợp lệ thật sự (mỗi ống chốt một lần), và chính xác với hai subtask đầu:
- Subtask 2 (mọi ~A_i = 0~): đáp án là ~C_{1N}~ (bất đẳng thức tam giác), thuật toán cho đúng giá trị này.
- Subtask 1 (thẳng hàng, ~x_1 < x_2 < \dots < x_n~): đi lần lượt ~1, 2, \dots, N~ là tối ưu. Thật vậy, xét lần đầu tiên một hành trình bất kỳ tới một ống có hoành độ ~\ge x_k~: trước đó nó chỉ ăn được các ~A_j~ với ~j < k~ và đã đi ít nhất ~x_k - x_1~, nên cần ~E \ge d(x_k - x_1) - \sum_{j<k} A_j~ — đúng bằng điều kiện của đường đi thẳng. Thuật toán tham lam chốt các ống theo đúng thứ tự này. Vậy đáp án subtask 1 là ~\max_k (d(x_k - x_1) - \sum_{1<j<k} A_j)~.</li>
Với trường hợp tổng quát (subtask 3), khi ~d~ nhỏ và ~A_i~ lớn có thể có "chu trình có lời", bài toán chính xác (mỗi ống dùng một lần) khó như bài đường đi thu thưởng; chưa có thuật toán đa thức chính xác, sub 2 cho một đáp án hợp lệ tốt.
Chương trình hoàn chỉnh
Main đọc dữ liệu (máy chấm dùng file MARIO.INP/MARIO.OUT), ~n \le 16~ gọi sub1 (chính xác), ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
long long d, A[105], X[105], Y[105], C[105][105]; // C[u][v] = d * khoảng cách Manhattan
const long long INF = 4e18;
// Sub 1: quy hoạch động trạng thái (tập đã đi, ống đang đứng) — chính xác, dùng khi n <= 16
// h[mask][u] = năng lượng tối thiểu cần có khi VỪA TỚI u (chưa cộng A[u]), đã đi qua tập mask (chứa u)
void sub1() {
int full = 1 << n;
vector<vector<long long>> h(full, vector<long long>(n, INF));
for (int mask = full - 1; mask >= 1; mask--)
for (int u = 0; u < n; u++) {
if (!(mask >> u & 1)) continue;
if (u == n - 1) { h[mask][u] = 0; continue; } // tới N là xong
long long best = INF;
for (int v = 0; v < n; v++) {
if (mask >> v & 1) continue; // mỗi ống chỉ dùng 1 lần
long long hv = h[mask | 1 << v][v];
if (hv < INF) best = min(best, hv + C[u][v] - A[u]);
}
if (best < INF) h[mask][u] = max(0LL, best); // khi tới u năng lượng phải >= 0
}
cout << h[1][0] << "\n";
}
// Kiểm tra: với năng lượng ban đầu E, đi tham lam "luôn mở rộng ống có năng lượng lớn nhất"
// (giống Dijkstra, mỗi ống chốt 1 lần) có tới được ống N không.
bool check(long long E) {
vector<long long> best(n, -1); // năng lượng lớn nhất khi vừa tới ống (chưa cộng A)
vector<bool> done(n, false);
best[0] = E;
while (true) {
int u = -1;
for (int i = 0; i < n; i++)
if (!done[i] && best[i] >= 0 && (u == -1 || best[i] > best[u])) u = i;
if (u == -1) return false;
if (u == n - 1) return true;
done[u] = true;
long long e = best[u] + A[u];
for (int v = 0; v < n; v++)
if (!done[v] && e - C[u][v] >= 0) best[v] = max(best[v], e - C[u][v]);
}
}
// Sub 2: chặt nhị phân năng lượng E + kiểm tra tham lam ở trên. O(n^2 log)
// Chính xác khi các ống thẳng hàng theo thứ tự (subtask 1) hoặc mọi A = 0 (subtask 2).
void sub2() {
long long lo = 0, hi = C[0][n - 1]; // đi thẳng 1 -> N luôn được với E = C[0][N-1]
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (check(mid)) hi = mid; else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
freopen("MARIO.INP", "r", stdin);
freopen("MARIO.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> d;
for (int i = 1; i < n - 1; i++) cin >> A[i]; // A[0] = A[n-1] = 0
for (int i = 0; i < n; i++) cin >> X[i] >> Y[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) C[i][j] = d * (llabs(X[i] - X[j]) + llabs(Y[i] - Y[j]));
if (n <= 16) sub1();
else sub2();
return 0;
}
Bình luận