Hướng dẫn giải của [Beginner Free Contest 10] TRAVELAB
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
Chia các công ty ~1..n~ thành hai dãy tăng dần (một dãy cho thanh tra A, một dãy cho B; mỗi dãy có thể rỗng), cộng quãng đường giữa các công ty liên tiếp trong mỗi dãy, tìm tổng nhỏ nhất. Chú ý ~d(s, t)~ không đối xứng và ta luôn đi từ công ty nhỏ sang công ty lớn hơn.
Sub 1: Vét cạn — ~O(2^n \cdot n)~, dùng khi ~n \le 20~
Thử mọi cách gán mỗi công ty cho A hoặc B bằng một mặt nạ bit, duyệt công ty từ 1 đến ~n~ và cộng quãng đường từ công ty trước đó của cùng người. Nếu chỉ nộp sub này: đúng 10/50 test.
Sub 2: Quy hoạch động — ~O(n^2)~
Sau khi đã xử lý công ty ~1..k~, một thanh tra chắc chắn đang ở công ty ~k~, người kia đang ở công ty ~j < k~ (~j = 0~ nếu chưa đi đâu). Gọi ~f[j]~ là tổng quãng đường nhỏ nhất. Chuyển sang công ty ~k+1~: hoặc người ở ~k~ đi tiếp (~f'[j] = f[j] + d(k, k+1)~), hoặc người ở ~j~ đi (~f'[k] = f[j] + d(j, k+1)~, với ~j=0~ thì chi phí 0). Mỗi bước ~O(k)~, tổng ~O(n^2)~. Đáp án là giá trị nhỏ nhất của ~f~ sau cùng; dùng ~long long~ cho an toàn. Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Main đọc ma trận ~d~ (máy chấm dùng đọc/ghi chuẩn); ~n \le 20~ gọi sub1, 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;
int d[1005][1005]; // d[i][j]: quãng đường từ công ty i đến công ty j (chỉ số từ 1)
// Sub 1: vét cạn 2^n cách chia các công ty cho A hoặc B, dùng khi n <= 20
void sub1() {
long long best = LLONG_MAX;
for (int mask = 0; mask < (1 << n); mask++) {
long long cost = 0;
int lastA = 0, lastB = 0; // 0 = chưa đi công ty nào
for (int i = 1; i <= n; i++) {
if (mask >> (i - 1) & 1) { if (lastA) cost += d[lastA][i]; lastA = i; }
else { if (lastB) cost += d[lastB][i]; lastB = i; }
}
best = min(best, cost);
}
printf("%lld\n", best);
}
// Sub 2: quy hoạch động O(n^2). Sau khi xử lý công ty 1..k, một thanh tra đang ở công ty k,
// người kia đang ở công ty j (j = 0: chưa đi đâu). f[j] = tổng quãng đường nhỏ nhất.
void sub2() {
const long long INF = LLONG_MAX / 4;
vector<long long> f(n + 1, INF), g(n + 1);
f[0] = 0; // k = 1: người kia chưa đi đâu
for (int k = 1; k < n; k++) {
fill(g.begin(), g.end(), INF);
for (int j = 0; j < k; j++) {
if (f[j] >= INF) continue;
// công ty k+1 do người đang ở k kiểm tra: người kia vẫn ở j
g[j] = min(g[j], f[j] + d[k][k + 1]);
// công ty k+1 do người đang ở j kiểm tra: khi đó người kia đứng ở k
g[k] = min(g[k], f[j] + (j ? d[j][k + 1] : 0));
}
f = g;
}
printf("%lld\n", *min_element(f.begin(), f.end()));
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &d[i][j]);
if (n <= 20) sub1();
else sub2();
return 0;
}
Bình luận