Hướng dẫn giải của [2526 KS CHV] Câu 3: Lựa chọn dự án
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