Hướng dẫn giải của [2526 KS CHV] Câu 3: Lựa chọn dự án


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 dự án, mỗi dự án có thời gian bắt đầu s, kết thúc f và lợi nhuận v. Chọn tập dự án không xung đột sao cho tổng lợi nhuận lớn nhất. Hai dự án i và j tương thích khi s[j] > f[i] hoặc s[i] > f[j].

Sub 1: Thử mọi tập con — ~O(2^N \cdot N)~, dùng khi ~N \le 20~

Với mỗi tập con, kiểm tra mọi cặp trong tập có tương thích không và cộng lợi nhuận. Dùng mặt nạ bit để kiểm tra nhanh. Sub này đúng 1/20 test, vì phần lớn test có N lớn hơn 20 nằm ngoài miền của nó.

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

Sắp xếp dự án theo f tăng dần. dp[i] = v[i] + max dp[j] với các j có f[j] < s[i]. Duyệt j trực tiếp. Sub này đúng 17/20 test.

Sub 3: Quy hoạch động với tìm nhị phân — ~O(N \log N)~

Sau khi sắp xếp theo f, các dự án có f < s[i] là một tiền tố của dãy, tìm độ dài tiền tố bằng lower_bound. Giữ mảng prefix max pm để lấy giá trị lớn nhất của tiền tố. Đúng 20/20 test.

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

Hàm main đọc N và các dự án. Nếu N \le 20 gọi sub 1, nếu N \le 1000 gọi sub 2, còn lại gọi sub 3.

#include <bits/stdc++.h>
using namespace std;

int n;
long long s[100005], f[100005], v[100005];   // dự án i: bắt đầu s[i], kết thúc f[i], lợi nhuận v[i]

// Sub 1: thử mọi tập con dự án, O(2^N * N) — dùng khi N <= 20
void sub1() {
    // comp[i] = mặt nạ các dự án j tương thích với i (j khác i)
    vector<int> comp(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && (s[j] > f[i] || s[i] > f[j])) comp[i] |= (1 << j);

    long long best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        bool ok = true;
        long long total = 0;
        for (int i = 0; i < n && ok; i++)
            if (mask >> i & 1) {
                // mọi dự án khác trong tập phải tương thích với i
                if ((mask & ~comp[i] & ~(1 << i)) != 0) ok = false;
                total += v[i];
            }
        if (ok) best = max(best, total);
    }
    cout << best << "\n";
}

// Sub 2: quy hoạch động O(N^2). Sắp xếp theo f tăng dần.
// dp[i] = lợi nhuận lớn nhất khi dự án i là dự án cuối cùng được chọn.
void sub2() {
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return f[a] < f[b]; });
    vector<long long> dp(n);
    long long best = 0;
    for (int x = 0; x < n; x++) {
        int i = idx[x];
        dp[x] = v[i];
        for (int y = 0; y < x; y++) {
            int j = idx[y];
            if (f[j] < s[i]) dp[x] = max(dp[x], dp[y] + v[i]);   // j kết thúc trước khi i bắt đầu
        }
        best = max(best, dp[x]);
    }
    cout << best << "\n";
}

// Sub 3: quy hoạch động + tìm nhị phân, O(N log N)
void sub3() {
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return f[a] < f[b]; });
    vector<long long> fs(n);   // f đã sắp xếp
    for (int x = 0; x < n; x++) fs[x] = f[idx[x]];
    vector<long long> pm(n + 1, 0);   // pm[k] = max dp của k dự án đầu tiên trong thứ tự f
    for (int x = 0; x < n; x++) {
        int i = idx[x];
        // số dự án có f[j] < s[i] là một tiền tố của dãy đã sắp xếp
        int k = lower_bound(fs.begin(), fs.end(), s[i]) - fs.begin();
        long long cur = pm[k] + v[i];
        pm[x + 1] = max(pm[x], cur);
    }
    cout << pm[n] << "\n";
}

int main() {
    freopen("CAU3.INP", "r", stdin);
    freopen("CAU3.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i] >> f[i] >> v[i];
    if (n <= 20) sub1();
    else if (n <= 1000) sub2();
    else sub3();
    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.