Hướng dẫn giải của [Beginner Free Contest 10] ELEVATOR
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Mỗi chuyến đi từ tầng 1 lên tầng cao nhất của nhóm rồi quay về tốn ~2(p_max - 1)~. Bài toán là chia N người thành các nhóm không quá K người sao cho tổng chi phí nhỏ nhất.
Sub 1: Quy hoạch bitmask - ~O(3^n)~, dùng khi ~n \le 15~
dp[mask] là chi phí nhỏ nhất để đưa đúng những người trong mask tới nơi. Với mỗi tập con khác rỗng s (tối đa K người) làm một chuyến thì cập nhật dp. Nếu chỉ nộp sub này: đúng 1/20 test.
Sub 2: Tham lam - ~O(n \log n)~
Sắp tầng giảm dần, cứ K người liên tiếp là một chuyến, chi phí chuyến là ~2(p - 1)~ với p là tầng của người xa nhất trong chuyến. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc N, K và các tầng. Nếu ~n \le 15~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, K;
vector<int> p; // p[i] = tang nguoi thu i muon toi
// Sub 1: quy hoach bitmask, moi buoc chon tap con s (<= K nguoi) di trong mot chuyen, cost = 2*(max-1)
// Sau khi sap tang, max cua tap con s la p[chi so bit cao nhat cua s]. Dung khi n <= 15.
void sub1() {
sort(p.begin(), p.end());
int full = (1 << n) - 1;
const long long INF = LLONG_MAX / 4;
vector<long long> dp(1 << n, INF);
dp[0] = 0;
for (int mask = 1; mask <= full; mask++) {
for (int s = mask; s > 0; s = (s - 1) & mask) {
if (__builtin_popcount(s) > K) continue;
int hi = 31 - __builtin_clz(s);
long long cost = dp[mask ^ s] + 2LL * (p[hi] - 1);
dp[mask] = min(dp[mask], cost);
}
}
cout << dp[full] << "\n";
}
// Sub 2: tham lam - sap giam dan, cu K nguoi xa nhat di chung mot chuyen. Dung cho n lon.
void sub2() {
sort(p.begin(), p.end(), greater<int>());
long long ans = 0;
for (int i = 0; i < n; i += K)
ans += 2LL * (p[i] - 1);
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> K;
p.resize(n);
for (auto& x : p) cin >> x;
if (n <= 15) sub1();
else sub2();
return 0;
}
Bình luận