Hướng dẫn giải của [2627 KS1] KHOINGHIEP


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.

Hướng dẫn giải

Cần chọn tập công ty phải mua quà để chi phí nhỏ nhất, các công ty còn lại tự hợp tác được khi đủ ~a_i~ công ty đã hợp tác.

Sub 1: Quy hoạch động bitmask — ~O(2^N \cdot N)~, dùng khi ~N \le 20~

~dp[mask]~ là chi phí nhỏ nhất để đã hợp tác đúng tập ~mask~. Thêm công ty ~i~: miễn phí nếu ~a_i \le~ số bit của ~mask~, ngược lại tốn ~b_i~. Nếu chỉ nộp sub này: đúng 10/40 test.

Sub 2: Tham lam + heap — ~O(N \log N)~

Có thể mua trước tập ~S~ rồi hợp tác miễn phí phần còn lại theo ~a~ tăng dần. Sắp theo ~a~ tăng dần (vị trí ~1..N~). Công ty ở vị trí ~i~ không phải mua cần có ít nhất ~a_i - i + 1~ công ty được mua ở các vị trí sau nó. Duyệt ~i~ từ ~N~ về 1, đưa ~b~ của công ty ~i~ vào min-heap; nếu số công ty đã mua chưa đủ thì lấy công ty rẻ nhất trong heap để mua (nếu đó chính là ~i~ thì ràng buộc của ~i~ biến mất). Đáp án là tổng chi phí các lần mua. Nếu chỉ nộp sub này: đúng 40/40 test.

Chương trình hoàn chỉnh

main đọc dữ liệu; ~N \le 20~ gọi sub1, lớn hơn 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 a[200005], b[200005];

// Sub 1: quy hoạch động theo tập công ty đã hợp tác — O(2^n * n), dùng khi n <= 20
void sub1() {
    int F = 1 << n;
    vector<int> dp(F, INT_MAX);
    dp[0] = 0;
    for (int mask = 0; mask < F; mask++) {
        if (dp[mask] == INT_MAX) continue;
        int e = __builtin_popcount(mask);
        for (int i = 0; i < n; i++) if (!(mask >> i & 1)) {
            int cost = dp[mask] + (a[i] <= e ? 0 : b[i]);   // đủ điều kiện thì miễn phí, không thì mua quà
            int nm = mask | (1 << i);
            dp[nm] = min(dp[nm], cost);
        }
    }
    cout << dp[F - 1] << "\n";
}

// Sub 2: tham lam + heap — O(n log n)
// Mua trước tập S công ty, rồi hợp tác miễn phí các công ty còn lại theo thứ tự a tăng dần.
// Sắp theo a tăng dần (vị trí 1..n). Công ty ở vị trí i không mua cần: số công ty được mua ở các vị trí sau i
// >= a_i - i + 1. Duyệt i từ n về 1: nếu chưa đủ thì mua công ty rẻ nhất trong các công ty đã xét (kể cả i).
void sub2() {
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int x, int y) { return a[x] < a[y]; });
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    long long cost = 0;
    int c = 0;                               // số công ty đã mua ở các vị trí sau i
    for (int i = n; i >= 1; i--) {
        int x = id[i - 1];
        pq.push({b[x], x});
        int need = a[x] - i + 1;
        while (c < need && !pq.empty()) {
            auto t = pq.top(); pq.pop();
            cost += t.first; c++;
            if (t.second == x) break;        // chính i được mua thì không còn ràng buộc
        }
    }
    cout << cost << "\n";
}

int main() {
    freopen("KHOINGHIEP.INP", "r", stdin);
    freopen("KHOINGHIEP.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    if (n <= 20) sub1();
    else sub2();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.